Loading [MathJax]/jax/output/HTML-CSS/jax.js

Python程序:查找能被a、b、c整除的序列的第n项


假设我们有四个数字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)
  • left := 1,right := 10^9
  • 当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
    • 如果numterms > n,则
      • right := mid - 1
    • 否则,如果numterms < n,则
      • left := mid + 1
    • 否则,
      • 返回 mid - min(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))

输入

8, 3, 7, 9

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

18

更新于:2020年12月12日

浏览量:307

开启您的职业生涯

完成课程获得认证

开始学习
广告