Pythonでa、b、cで割り切れるシーケンスのn番目の項を見つけるプログラム

n、a、b、cの4つの数があるとします。 a、b、またはcで割り切れる数列のソートされたシーケンスのn番目（インデックス付き0）の項を見つける必要があります。

したがって、入力がn =8 a =3 b =7 c =9の場合、シーケンスの最初の9項は[1、3、6、7、9、12、14であるため、出力は18になります。 、15、18]。

これを解決するには、次の手順に従います-

• a、b、cの最小値が1と同じ場合、
  • return n
• ab：=lcm（a、b）、bc：=lcm（b、c）、ca：=lcm（a、c）
• abc：=lcm（ab、c）
• 左：=1、右：=10 ^ 9
• 左<=右、実行
  • mid：=（左+右）/ 2
  • na：=midの商/a
  • nb：=mid/bの商
  • nc：=mid/cの商
  • nab：=mid/abの商
  • nbc：=mid/bcの商
  • nca：=mid/caの商
  • nabc：=mid/abcの商
  • numterms：=na + nb + nc --nab --nbc --nca + nabc
  • numterms> nの場合、
    • 右：=半ば-1
  • それ以外の場合、numterms
  • 左：=半ば+ 1
• それ以外の場合、
  • return mid-最小値（mid mod a、mid mod b、mid mod c）

例（Python）

理解を深めるために、次の実装を見てみましょう-

import math
def lcm(a, b):
   return (a * b) // math.gcd(a, b)
class Solution:
   def solve(self, n, a, b, c):
      if min(a, b, c) == 1:
         return n
      ab, bc, ca = lcm(a, b), lcm(b, c), lcm(a, c)
      abc = lcm(ab, c)
      left, right = 1, 10 ** 9
      while left <= right:
         mid = (left + right) // 2
         na = mid // a
         nb = mid // b
         nc = mid // c
         nab = mid // ab
         nbc = mid // bc
         nca = mid // ca
         nabc = mid // abc
         numterms = na + nb + nc - nab - nbc - nca + nabc
         if numterms > n:
            right = mid - 1
         elif numterms < n:
            left = mid + 1
         else:
            return mid - min(mid % a, mid % b, mid % c)
      return -1
ob = Solution()
n = 8
a = 3
b = 7
c = 9
print(ob.solve(n, a, b, c))

入力

8, 3, 7, 9

出力

18