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
广告