Hiểu bài toán

Bài toán yêu cầu đếm số lượng số nguyên trong khoảng từ A đến B (A ≤ B) mà chia hết cho ít nhất một trong hai số C hoặc D. Nói cách khác, ta cần tìm số lượng số nguyên X sao cho A ≤ X ≤ B và (X chia hết cho C) hoặc (X chia hết cho D).

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

Cách Công thức Bổ sung (Inclusion-Exclusion)

#include <iostream>
using namespace std;

long long gcd(long long a, long long b) {
    while (b) {
        long long tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

long long cnt(long long a, long long b, long long c) {
    if (c > b) return 0;
    if (c < a) {
        long long start = a + (c - a % c) % c;
        if (start > b) return 0;
        return (b - start) / c + 1;
    }
    return (b / c) - ((a - 1) / c);
}

int main() {
    freopen("cntnum.inp", "r", stdin);
    freopen("cntnum.out", "w", stdout);
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    long long bcnn = (c / gcd(c, d)) * d;
    cout << (b - a + 1) - (cnt(a, b, c) + cnt(a, b, d) - cnt(a, b, bcnn));
    return 0;
}

• Time Complexity: O(log(min(c, d)))
• Space Complexity: O(1)

Đây là cách tiếp cận hiệu quả nhất dựa trên Nguyên lý Bổ sung (Inclusion-Exclusion Principle).

1. Số lượng số trong khoảng [A, B] chia hết cho C là floor(B/C) - floor((A-1)/C).
2. Tương tự cho D.
3. Các số chia hết cho cả C và D là các số chia hết cho Bội chung nhỏ nhất (BCNN) của C và D. Số lượng là floor(B/BCNN) - floor((A-1)/BCNN).
4. Số lượng số chia hết cho C hoặc D = (Số chia hết C) + (Số chia hết D) - (Số chia hết cả C và D).
5. Kết quả cuối cùng là (B - A + 1) trừ đi số lượng tìm được ở bước 4 (vì bài hỏi đếm số không chia hết cho C hoặc D). Phương pháp này chạy siêu nhanh ngay cả với số lớn (đến 10^18).

Cách Tối ưu hóa vòng lặp (Loop Optimization)

#include <iostream>
using namespace std;

long long cnt(long long a, long long b, long long c) {
    if (c > b) return 0;
    long long begin = a;
    if (c > a && c < b) {
        begin = c;
    } else if (c > b) {
        return 0;
    } else {
        while (begin % c != 0) {
            ++begin;
        }
    }
    long long res = (b - begin) / c + 1;
    return res;
}

int main() {
    freopen("cntnum.inp", "r", stdin);
    freopen("cntnum.out", "w", stdout);
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    long long bcnn = (c * d) / gcd(c, d); // Hàm gcd giả định
    cout << (b - a + 1) - (cnt(a, b, c) + cnt(a, b, d) - cnt(a, b, bcnn));
    return 0;
}

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

Đây là biến thể của phương pháp tối ưu, sử dụng hàm cnt để đếm số lượng số chia hết cho K trong khoảng [A, B]. Thay vì dùng công thức chia lấy thương trực tiếp, hàm này tìm số chia hết cho K đầu tiên trong khoảng (bằng cách cộng dồn hoặc kiểm tra điều kiện) rồi tính số lượng còn lại. Cách này về bản chất vẫn là toán học (O(1) do chỉ là phép chia), nhưng mã nguồn có vẻ phức tạp hơn một chút so với cách dùng floor trực tiếp. Tuy nhiên, nó vẫn đảm bảo hiệu năng tốt.

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

Bài học kinh nghiệm

• Bài toán đếm số chia hết có thể giải quyết hiệu quả bằng công thức toán học thay vì duyệt tuần tự.
• Nguyên lý Bổ sung (Inclusion-Exclusion) là chìa khóa để xử lý bài toán 'tổng của hai tập hợp' (chia hết cho A hoặc B) mà không bị đếm trùng.
• Bài toán "Đếm số" thường yêu cầu kết quả là số lượng số không thỏa mãn điều kiện, hãy chú ý phép toán cuối cùng.

Lỗi thường gặp

• Sử dụng vòng lặp để duyệt từ A đến B sẽ gây lỗi thời gian (Time Limit Exceeded) vì A, B có thể lên tới 10^18.
• Tính BCNN sai (lỗi số quá lớn): Phải dùng công thức (C / gcd(C, D)) * D thay vì C * D để tránh tràn số (overflow) đối với số nguyên 64-bit.
• Xử lý sai trường hợp số chia hết (ví dụ khi A > C, hoặc A = C). Hàm cnt cần xử lý chính xác việc tìm số chia hết đầu tiên trong khoảng.