Chương trình tìm số hạng thứ n của dãy chia hết cho a, b, hoặc c trong Python

Cho n, a, b, c. Tìm số hạng thứ n (0-indexed) của dãy số tăng dần chia hết cho a hoặc b hoặc c.

Ví dụ: n=8, a=3, b=7, c=9 → dãy: [3,6,7,9,12,14,15,18,...] → số hạng thứ 8 là 18.

Giải thuật (Tìm kiếm nhị phân + Nguyên lý bao hàm - loại trừ)

• Nếu min(a,b,c)==1 → trả về n (mọi số đều chia hết cho 1).
• Tính LCM các cặp và LCM của ba số.
• Tìm kiếm nhị phân trên khoảng [1, 10⁹] giá trị mid sao cho số lượng số ≤ mid chia hết cho a/b/c bằng n+1 (do 0-indexed).
• Số lượng = mid//a + mid//b + mid//c - mid//lcm(a,b) - mid//lcm(b,c) - mid//lcm(a,c) + mid//lcm(a,b,c).
• Khi tìm thấy, điều chỉnh xuống bội số gần nhất.

Mã nguồn 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, nb, nc = mid//a, mid//b, mid//c
            nab, nbc, nca = mid//ab, mid//bc, mid//ca
            nabc = mid//abc
            cnt = na + nb + nc - nab - nbc - nca + nabc
            if cnt > n:
                right = mid - 1
            elif cnt < n:
                left = mid + 1
            else:
                return mid - min(mid % a, mid % b, mid % c)
        return -1

ob = Solution()
n, a, b, c = 8, 3, 7, 9
print(ob.solve(n, a, b, c))  # Output: 18

Đầu vào

8, 3, 7, 9

Đầu ra

18