Hiểu bài toán

Bài toán yêu cầu đếm số số nguyên dương nhỏ hơn hoặc bằng N không chia hết cho bất kỳ số nguyên tố nào trong khoảng [2, K]. Nói cách khác, đó là số lượng số nguyên dương từ 1 đến N mà ước nguyên tố nhỏ nhất của chúng lớn hơn K. Với N có thể lên tới 10^12 và K nhỏ (ví dụ K=19), ta cần một cách tiếp cận hiệu quả hơn brute force.

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

Cách Quy hoạch động dựa trên số nguyên tố (Sieve-like DP)

#include <bits/stdc++.h>
using namespace std;
int a[9] = {0, 2, 3, 5, 7, 11, 13, 17, 19};

long long slove(long long N, int K){
    if (K == 2){
        return N / K;
    }else{
        long long res = N / K;
        long long temp = 0;
        for (int i = 1; i < 9; i++){
            if (a[i] >= K){
                return res - temp;
            }else{
                temp = temp + slove(res, a[i]);
            }
        }
        return res;
    }
}

int main()
{
    freopen("bonus.inp","r",stdin);
    freopen("bonus.out","w",stdout);
    long long n;
    long long res;
    int k;
    cin >> n >> k;
    res = n;
    for (int i = 1; i <= 8; i++)
    {
        if (a[i] <= k){
            res = res - slove(n, a[i]);
        }else{
            break;
        }
    }
    cout<<res;
}

• Time Complexity: O(2^P) hoặc O(P!) (P là số số nguyên tố <= K, rất nhỏ, <= 8)
• Space Complexity: O(P)

Phương pháp này dựa trên Nguyên lý Bao hàm loại trừ (Inclusion-Exclusion Principle) một cách gián tiếp. Nó đếm số lượng số chia hết cho ít nhất một số trong tập {2, ..., K} và trừ nó từ N. Hàm slove(N, K) tính số lượng số chia hết cho K nhưng không chia hết cho bất kỳ số nguyên tố nào nhỏ hơn K (và nguyên tố với K). Logic:

1. res = N / K: Đây là số lượng số chia hết cho K.
2. temp được dùng để trừ đi các số bị đếm thừa (các số chia hết cho K và cả các số nguyên tố nhỏ hơn K, tức là các bội số chung).
3. Vòng lặp for gọi đệ quy slove(N/K, a[i]) với các a[i] < K. Hàm này trả về số lượng số trong tập N/K có ước nguyên tố nhỏ nhất là a[i]. Khi cộng dồn temp, ta đang trừ đi các số chia hết cho K và các ước nguyên tố nhỏ hơn.
4. main gọi vòng lặp để trừ đi từng phần: res -= slove(n, p) với mỗi p <= K. Cuối cùng, res chính là số lượng số không chia hết cho bất kỳ số nào trong [2, K].

Cách Bao hàm loại trừ (Inclusion-Exclusion)

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

#define int long long

// Tính số lượng số chia hết cho ít nhất 1 số trong [2..k]
int count_bad(int n, int k) {
    vector<int> a;
    for (int i = 2; i <= k; ++i) {
        a.push_back(i);
    }

    int m = a.size();
    int res = 0;

    for (int mask = 1; mask < (1 << m); ++mask) {
        int lcm = 1;
        bool overflow = false;

        for (int i = 0; i < m; ++i) {
            if ((mask >> i) & 1) {
                int g = __gcd(lcm, a[i]);
                if (lcm / g > n / a[i]) { // tránh tràn số
                    overflow = true;
                    break;
                }
                lcm = lcm / g * a[i];
            }
        }

        if (overflow || lcm > n) continue;

        int bits = __builtin_popcount(mask);
        if (bits % 2 == 1)
            res += n / lcm;
        else
            res -= n / lcm;
    }

    return res;
}

signed main() {
    freopen("BONUS.INP", "r", stdin);
    freopen("BONUS.OUT", "w", stdout);
    int n, k;
    cin >> n >> k;
    int bad = count_bad(n, k);
    cout << n - bad;
}

• Time Complexity: O(2^(K-1))
• Space Complexity: O(K)

Đây là cách tiếp cận trực tiếp của Nguyên lý Bao hàm loại trừ (Inclusion-Exclusion Principle - IEP). Mục tiêu: Đếm số số x <= N sao cho x chia hết cho ít nhất một số trong S = {2, 3, ..., K}. Công thức: |A_2 U A_3 U ... U A_K| = sum |A_i| - sum |A_i intersect A_j| + ... Thay vì liệt kê tất cả các số, ta duyệt qua các tập hợp con (đại diện bằng bitmask) của S.

• Với mỗi tập hợp con, tính Bội chung nhỏ nhất (LCM) của các phần tử trong tập hợp.
• Nếu kích thước tập hợp là lẻ, cộng N / LCM vào.
• Nếu kích thước tập hợp là chẵn, trừ N / LCM ra. Số lượng số không chia hết cho số nào là N - |Union|.

Cách Brute Force (Chỉ dùng cho kiểm tra)

#include <iostream>
using namespace std;

int main() {
    // Pseudo-code
    long long N; int K;
    cin >> N >> K;
    long long count = 0;
    for(int i = 1; i <= N; i++) {
        bool ok = true;
        for(int j = 2; j <= K; j++) {
            if(i % j == 0) {
                ok = false;
                break;
            }
        }
        if(ok) count++;
    }
    cout << count;
}

• Time Complexity: O(N*K)
• Space Complexity: O(1)

Duyệt qua từng số từ 1 đến N, kiểm tra xem số đó có chia hết cho bất kỳ số nào từ 2 đến K không.

• Nếu không chia hết cho số nào, tăng biến đếm. Cách này chỉ hiệu quả khi N rất nhỏ (ví dụ N <= 10^6). Với N lên tới 10^12, nó chắc chắn sẽ bị Time Limit Exceeded.

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

Bài học kinh nghiệm

• Bài toán này là bài toán đếm số lượng số có ước nguyên tố nhỏ nhất (smallest prime factor - SPF) lớn hơn K.
• Vì K rất nhỏ (<= 19), số lượng số nguyên tố cần xét rất ít (8 số), nên các thuật toán có độ phức tạp theo số lượng số nguyên tố (như 2^P) là chấp nhận được.
• Phương pháp của Solution 1 là một dạng tối ưu hóa của Inclusion-Exclusion, hoặc có thể nhìn nhận là quy hoạch động dựa trên các ước nguyên tố.

Lỗi thường gặp

• Lỗi tràn số (Integer Overflow) khi tính LCM của các số lớn. Cần kiểm tra điều kiện trước khi nhân.
• Sai lệch trong việc áp dụng Inclusion-Exclusion (ví dụ: quên dấu trừ, nhầm lẫn giữa phép chia hết và không chia hết).
• Xử lý sai số lượng số nguyên tố cần xét (ví dụ: quên các số 2, 3... hoặc nhầm thứ tự).