Hiểu bài toán

Cho ba số nguyên dương N, x, y (các giá trị có thể lên tới 10^12). Yêu cầu đếm số lượng số nguyên dương trong khoảng từ 1 đến N (bao gồm N) mà chia hết cho cả x và y. Nói cách khác, tìm số lượng bội chung của x và y không vượt quá N.

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

Cách Duyệt qua các bội của BCNN

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

long long ucln(long long a, long long b) {
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    long long n, x, y;
    cin >> n >> x >> y;

    long long bcnn = x / ucln(x, y) * y; 
    cout << n / bcnn;

    return 0;
}

• Time Complexity: O(log(min(x, y)))
• Space Complexity: O(1)

Một số chia hết cho cả x và y thì nó phải chia hết cho Bội chung nhỏ nhất (BCNN) của x và y. Vậy bài toán quy về đếm số lượng số nguyên dương không vượt quá N mà chia hết cho BCNN(x, y). Số lượng này được tính bằng cách lấy N chia nguyên cho BCNN.

Bước 1: Tính Ước chung lớn nhất (UCLN) của x và y bằng Thuật toán Euclid. Bước 2: Tính BCNN theo công thức: BCNN(x, y) = (x * y) / UCLN(x, y). Để tránh tràn số (overflow) khi x và y lớn, ta tính BCNN = (x / UCLN(x, y)) * y. Bước 3: Kết quả là N chia lấy nguyên cho BCNN.

Độ phức tạp: O(log(min(x, y))) do thuật toán Euclid, không gian O(1).

Cách Công thức trực tiếp

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

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    long long N, x, y;
    cin >> N >> x >> y;

    long long lcm = x / gcd(x, y) * y;
    cout << N / lcm;

    return 0;
}

• Time Complexity: O(log(min(x, y)))
• Space Complexity: O(1)

Đây là cách tiếp cận tối ưu và ngắn gọn nhất. Nó dựa trên nhận thức toán học rằng tập hợp các số chia hết cho cả A và B chính là tập hợp các số chia hết cho BCNN(A, B). Do đó, số lượng số trong [1, N] chia hết cho cả x và y bằng số lượng số trong [1, N] chia hết cho BCNN(x, y).

Công thức: Kết quả = N / ((x * y) / gcd(x, y)). Để tránh tràn số, ta tính BCNN = (x / gcd(x, y)) * y.

Các giải pháp đã cho (lch101, truongik, nhatminhhtm) đều áp dụng phương pháp này với các biến thể nhỏ về cách đặt tên hàm (gcd/ucln) hoặc cách viết vòng lặp đệ quy/ko đệ quy.

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

Bài học kinh nghiệm

• Một số chia hết cho cả x và y thì nó chia hết cho BCNN(x, y).
• Số lượng số chia hết cho K trong đoạn [1, N] là N / K (phép chia nguyên).
• Công thức BCNN(a, b) = (a * b) / UCLN(a, b). Để tránh tràn số với a, b lớn, ta tính (a / UCLN(a, b)) * b.

Lỗi thường gặp

• Tràn số (Integer Overflow) khi thực hiện phép nhân x * y nếu x, y lớn (lên tới 10^12). Cần chia cho UCLN trước.
• Sử dụng sai kiểu dữ liệu (ví dụ: int thay vì long long) dẫn đến sai kết quả trên dữ liệu lớn.
• Lầm tưởng rằng chỉ cần đếm số chia hết cho x cộng với số chia hết cho y rồi trừ đi số chia hết cho cả hai (Nguyên lý Bổ sung) là đủ. Tuy nhiên, cách này chỉ đúng nếu hỏi về tổng số lượng số chia hết cho x HOẶC y. Ở đây yêu cầu chia hết cho x VÀ y, nên cách hiệu quả nhất là dùng BCNN.