Tìm số hạng thứ N chia hết cho A hoặc B trong C++

Cho A, B, N. Tìm số nguyên thứ N chia hết cho A hoặc B.

Ví dụ: A=4, B=3, N=5 → dãy: 3,4,6,8,9... → kết quả 9.

Giải pháp 1: Duyệt tuyến tính (O(N))

int findNTerm(int N, int A, int B) {
    int count = 0, num = 1;
    while (count < N) {
        if (num % A == 0 || num % B == 0) count++;
        if (count == N) return num;
        num++;
    }
    return 0;
}

Giải pháp 2: Tìm kiếm nhị phân (O(log(max)))

Sử dụng công thức đếm: count(x) = x/A + x/B - x/LCM(A,B). Tìm x nhỏ nhất sao cho count(x) >= N.

int findLCM(int a, int b) {
    int lcm = a;
    while (lcm % b != 0) lcm += a;
    return lcm;
}

int findNTerm(int N, int A, int B) {
    int lcm = findLCM(A, B);
    int low = 1, high = N * A * B;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (mid/A + mid/B - mid/lcm < N) low = mid + 1;
        else high = mid;
    }
    return low;
}

Đầu ra

12th term divisible by 3 or 4 is 24