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

假设我们有四个数字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]。

要解决这个问题，我们将遵循以下步骤：

如果a、b、c的最小值与1相同，则
- 返回n
ab：= lcm(a，b)，bc：= lcm(b，c)，ca：= lcm(a，c)
abc：= lcm(ab，c)
左：= 1，右：= 10^9
当左<=右时，执行以下操作
- 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
- 如果numterms > n，则
  - right：= mid – 1
- 否则，当numterms< n时，则
  - left：= mid + 1
- 否则，
  - 返回mid – (mid mod a、mid mod b、mid mod c）的最小值
返回-1

示例（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))