Bội số thứ N trong danh sách hợp nhất bội của 2 số C++

Cho x, y, n. Liệt kê bội số của x và y, gộp, sắp xếp, lấy phần tử thứ n.

Ví dụ

x=2, y=3, n=7
Bội 2: 2,4,6,8,10,12,14
Bội 3: 3,6,9,12,15,18,21
Hợp nhất sắp xếp: 2,3,4,6,8,9,10,12,14,15,18,21 → phần tử 7 là 10

Thuật toán tối ưu (Binary Search + LCM)

Số lượng bội ≤ mid là: mid/x + mid/y - mid/lcm(x,y). Dùng binary search tìm mid nhỏ nhất có count ≥ n.

Triển khai C++ (Binary Search O(log N))

#include <bits/stdc++.h>
using namespace std;

long long gcd(long long a, long long b) { return b ? gcd(b, a%b) : a; }
long long lcm(long long a, long long b) { return a / gcd(a,b) * b; }

int nthMultiple(int x, int y, int n) {
    long long l = lcm(x, y);
    long long lo = 1, hi = 1LL * min(x, y) * n;
    while (lo < hi) {
        long long mid = (lo + hi) / 2;
        long long cnt = mid/x + mid/y - mid/l;
        if (cnt >= n) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

int main() {
    cout << nthMultiple(2, 3, 7) << endl; // 10
    return 0;
}

Kết quả

10