Hướng dẫn giải

Đếm các số từ 1 đến ~N~ chia hết cho đúng một trong hai số nguyên tố ~A~, ~B~ (chia hết cho cả hai thì không tính).

Sub 1: Vét cạn — ~O(N)~, dùng khi ~N \le 10^6~

Duyệt từng ~x = 1..N~, kiểm tra ~x~ chia hết cho ~A~ và cho ~B~; đếm khi hai kết quả khác nhau. Nếu chỉ nộp sub này: đúng 38/40 test (2 test lớn bị quá thời gian).

Sub 2: Bao hàm – loại trừ — ~O(1)~

Số bội của ~A~ là ~\lfloor N/A \rfloor~, của ~B~ là ~\lfloor N/B \rfloor~, của cả hai là ~\lfloor N/\text{lcm}(A,B) \rfloor~. Đáp án = ~\lfloor N/A \rfloor + \lfloor N/B \rfloor - 2 \cdot \lfloor N/\text{lcm} \rfloor~. Trường hợp ~A = B~ thì lcm = ~A~, đáp án bằng 0 (đúng, vì số nào chia hết cho ~A~ cũng chia hết cho ~B~). Nếu chỉ nộp sub này: đúng 40/40 test.

Chương trình hoàn chỉnh

main đọc ~N, A, B~; ~N \le 10^6~ gọi sub1, lớn hơn gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.

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

long long N, A, B;

// Sub 1: duyệt từng số từ 1 đến N, đếm số chia hết đúng một trong A, B — O(N), dùng khi N <= 10^6
void sub1() {
    long long cnt = 0;
    for (long long x = 1; x <= N; x++) {
        bool a = (x % A == 0), b = (x % B == 0);
        if (a != b) cnt++;
    }
    cout << cnt << "\n";
}

// Sub 2: bao hàm - loại trừ — O(1)
void sub2() {
    long long l = A / __gcd(A, B) * B;           // bội chung nhỏ nhất
    long long both = N / l;                      // chia hết cả hai
    cout << N / A + N / B - 2 * both << "\n";
}

int main() {
    freopen("CHIAHET.INP", "r", stdin);
    freopen("CHIAHET.OUT", "w", stdout);
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> A >> B;
    if (N <= 1000000) sub1();
    else sub2();
    return 0;
}