สมมติว่าเรามีตัวเลข 4 ตัว n, a, b, c ต้องการหาพจน์ที่ n (0-indexed) ของลำดับที่เรียงลำดับของตัวเลขที่หารด้วย a หรือ b หรือ c ลงตัว
เช่น n = 8, a = 3, b = 7, c = 9 ผลลัพธ์ = 18 9 พจน์แรก: [1, 3, 6, 7, 9, 12, 14, 15, 18] (หมายเหตุ: 1 หารด้วยอะไรได้บ้าง? ตรงนี้อาจมีข้อผิดพลาดในตัวอย่างต้นฉบับ)
ขั้นตอนการแก้ปัญหา (Binary Search + Inclusion-Exclusion)
- ถ้า
min(a,b,c) == 1คืนn - คำนวณ LCM:
ab = lcm(a,b), bc = lcm(b,c), ca = lcm(a,c), abc = lcm(ab,c) - Binary search
left=1, right=10^9:mid = (left+right)//2- นับจำนวน ≤ mid ที่หารด้วย a,b,c ลงตัว:
numterms = mid//a + mid//b + mid//c - mid//ab - mid//bc - mid//ca + mid//abc - ถ้า
numterms > n:right = mid-1 - ถ้า
numterms < n:left = mid+1 - มิฉะนั้น: คืน
mid - min(mid%a, mid%b, mid%c)
- คืน -1
ตัวอย่างโค้ด
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
