Hiểu bài toán

Cho bốn số nguyên dương L, R, a, b. Yêu cầu đếm số lượng số nguyên x trong đoạn [L, R] sao cho x chia hết cho a hoặc chia hết cho b. Dải giá trị L, R có thể lên tới 10^18, trong khi a, b nhỏ (≤ 100).

Các cách tiếp cận

Cách Brute Force (Duyệt tuần tự)

long long count = 0;
for(long long i = L; i <= R; i++) {
    if(i % a == 0 || i % b == 0) count++;
}
cout << count;

• Time Complexity: O(R - L)
• Space Complexity: O(1)

Duyệt qua từng số trong đoạn [L, R] và kiểm tra xem nó có chia hết cho a hoặc b không. Với R-L lên tới 10^18, cách này quá chậm và chắc chắn bị TLE.

Cách Tập hợp bội số (Lập công thức)

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

long long countMultiples(long long n, long long k) {
    if (n <= 0) return 0;
    return n / k;
}

int main() {
    long long L, R, a, b;
    cin >> L >> R L >> a b >> a;
    // Đếm số bội của a trong [1, R]: R/a
    // Đếm số bội của a trong [1, L-1]: (L-1)/a
    // Số bội của a trong [L, R] = R/a - (L-1)/a
    long long kqa = R / a - (L - 1) / a;
    long long kqb = R / b - (L - 1) / b;

    // Bội chung nhỏ nhất của a và b
    long long bcnn = (a * b) / __gcd(a, b);
    long long kqab = R / bcnn - (L - 1) / bcnn;

    // Công thức bù trừ: |A ∪ B| = |A| + |B| - |A ∩ B|
    cout << kqa + kqb - kqab;
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Sử dụng quy tắc bù trừ của tập hợp. Số lượng số chia hết cho a trong [L, R] bằng số lượng số chia hết cho a trong [1, R] trừ đi số lượng trong [1, L-1]. Tương tự cho b. Tuy nhiên, các số chia hết cho cả a và b (tức là bội của BCNN(a, b)) bị đếm 2 lần nên cần trừ đi một lần. Độ phức tạp hoàn toàn hằng số, xử lý được dải giá trị lớn.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Sử dụng công thức đếm bội số trong đoạn [1, N]: floor(N / k). Số bội trong [L, R] = floor(R / k) - floor((L-1) / k).
• Áp dụng nguyên lý bù trừ tập hợp: |A ∪ B| = |A| + |B| - |A ∩ B|. Với A là tập bội của a, B là tập bội của b.
• Bội chung của a và b là bội của BCNN(a, b) = (a * b) / GCD(a, b).

Lỗi thường gặp

• Tràn số nguyên nếu tính a * b trước khi chia GCD (dù a, b nhỏ nhưng vẫn nên an toàn).
• Sai lệch khi tính số bội trong đoạn [L, R] nếu không trừ đi số bội trong [1, L-1] đúng cách.
• Quên kiểm tra điều kiện L > R (trong bài này ràng buộc L ≤ R).