程序以在Python中找到可被a，b，c整除的序列的第n个项

• Z时代
• 2024-01-10
• 分类：综合

假设我们有四个数字n，a，b和c。我们必须找到被a，b或c整除的数字排序序列的第n个（索引为0）。

因此，如果输入像n = 8 a = 3 b = 7 c = 9，那么输出将为18，如序列的前9个项是[1、3、6、7、9、12、14 ，15、18]。

范例(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

以上是 程序以在Python中找到可被a，b，c整除的序列的第n个项 的全部内容， 来源链接： utcz.com/z/321473.html