在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))
输入
8、3、7、9
输出
18