Hiểu bài toán

Cho các số nguyên dương a, b (1 ≤ a ≤ b ≤ 10^6). Đếm số lượng số nguyên dương x ∈ [a, b] có đúng 3 ước số nguyên tố phân biệt. Ví dụ, nếu x = p1 * p2 * p3 với p1, p2, p3 là các số nguyên tố phân biệt, thì x có đúng 3 ước số nguyên tố. Yêu cầu xử lý nhiều truy vấn (Q).

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

Cách Sàng Eratosthenes & Tiền xử lý

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

const int MAX = 1e6 + 5;
int prime_div_cnt[MAX];
int pref[MAX];

void sieve() {
    // prime_div_cnt[i] sẽ lưu số lượng ước nguyên tố phân biệt của i
    // Khởi tạo mảng có thể không cần thiết nếu dùng global, nhưng cẩn thận
    for (int i = 2; i < MAX; ++i) {
        if (prime_div_cnt[i] == 0) { // i là số nguyên tố
            for (int j = i; j < MAX; j += i) {
                prime_div_cnt[j]++;
            }
        }
    }

    // Xây dựng mảng tổng tiền tố
    for (int i = 1; i < MAX; ++i) {
        pref[i] = pref[i-1] + (prime_div_cnt[i] == 3);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    sieve();

    int q;
    cin >> q;
    while(q--) {
        int a, b;
        cin >> a >> b;
        cout << pref[b] - pref[a-1] << "\n";
    }
    return 0;
}

• Time Complexity: O(N log log N + Q)
• Space Complexity: O(N)

Phương pháp này sử dụng sàng Eratosthenes biến thể.

1. Tạo mảng prime_div_cnt để đếm số lượng ước nguyên tố phân biệt của mỗi số từ 1 đến 10^6. Với mỗi số nguyên tố p, ta tăng prime_div_cnt[j] cho mọi bội số j của p.
2. Nếu một số x có đúng 3 ước nguyên tố phân biệt, ví dụ p1, p2, p3, thì x phải là bội số của p1, p2, p3. Do đó, prime_div_cnt[x] sẽ bằng 3.
3. Xây dựng mảng tổng tiền tố pref để lưu số lượng số thỏa mãn điều kiện từ 1 đến i.
4. Với mỗi truy vấn [a, b], kết quả là pref[b] - pref[a-1]. Độ phức tạp tiền xử lý là O(N log log N), truy vấn O(1).

Cách Tối ưu hóa sàng (Sàng Eratosthenes cơ bản)

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

const int n = 1e6 + 1;
int cnt[n]; // cnt[i] = số lượng ước nguyên tố phân biệt của i
int pref[n];

void solve() {
    // Sàng để đếm số lượng ước nguyên tố
    // Chỉ cần duyệt các số i từ 2 đến n
    // Nếu cnt[i] == 0, tức i là số nguyên tố, thì xử lý bội số
    for (int i = 2; i < n; ++i) {
        if (cnt[i] == 0) {
            for (int j = i; j < n; j += i) {
                cnt[j]++;
            }
        }
    }

    // Tính mảng tiền tố
    for (int i = 1; i < n; ++i) {
        pref[i] = pref[i - 1] + (cnt[i] == 3);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    solve();

    int q;
    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << pref[b] - pref[a - 1] << "\n";
    }
    return 0;
}

• Time Complexity: O(N log log N + Q)
• Space Complexity: O(N)

Đây là phiên bản tối ưu hóa của phương pháp 1.

• Mảng cnt được sử dụng để đếm trực tiếp số lượng ước nguyên tố phân biệt.
• Vòng lặp for(int i=2; i<n; i++) kết hợp kiểm tra if(cnt[i]==0) để xác định số nguyên tố và cập nhật các bội số.
• Logic tính toán và truy vấn tương tự như cách 1.
• Đây là cách phổ biến nhất và hiệu quả trong các kỳ thi lập trình cho giới hạn 10^6.

Cách Brute Force (Không khuyến khích)

#include <iostream>
#include <vector>
using namespace std;

bool hasThreePrimeFactors(int n) {
    int count = 0;
    int temp = n;
    // Phân tích thừa số nguyên tố
    for (int i = 2; i * i <= temp; ++i) {
        if (temp % i == 0) {
            count++;
            while (temp % i == 0) temp /= i;
        }
    }
    if (temp > 1) count++;
    return count == 3;
}

int main() {
    int a, b;
    if (!(cin >> a >> b)) return 0;
    int ans = 0;
    for (int i = a; i <= b; ++i) {
        if (hasThreePrimeFactors(i)) ans++;
    }
    cout << ans << endl;
    return 0;
}

• Time Complexity: O((b-a) * sqrt(b)) ~ 10^12 (chậm)
• Space Complexity: O(1)

Phương pháp này kiểm tra từng số x trong khoảng [a, b]. Với mỗi x, ta phân tích thừa số nguyên tố và đếm số lượng ước nguyên tố phân biệt.

• Nếu số lượng bằng 3, tăng biến đếm.
• Phương pháp này quá chậm do độ phức tạp cao, không thể xử lý Q truy vấn hoặc dải số lớn 10^6.

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

Bài học kinh nghiệm

• Bài toán yêu cầu đếm số có đúng 3 ước nguyên tố phân biệt. Điều này đồng nghĩa với việc số đó là tích của 3 số nguyên tố phân biệt (ví dụ: p1 * p2 * p3).
• Sử dụng sàng Eratosthenes để đếm số lượng ước nguyên tố cho tất cả các số từ 1 đến N (10^6) là bước tiền xử lý tối ưu.
• Sử dụng mảng tổng tiền tố (Prefix Sum) cho phép trả lời mỗi truy vấn trong thời gian O(1).

Lỗi thường gặp

• Quên xử lý các số nguyên tố lớn hơn căn bậc hai của N (số nguyên tố còn lại sau vòng lặp phân tích thừa số).
• Lỗi kiểu dữ liệu: Nên dùng long long cho các biến liên quan đến phép nhân nếu limite lớn hơn 10^9, nhưng với N=10^6 thì int là đủ.
• Sai logic khi kiểm tra số lượng ước nguyên tố: Phải đảm bảo đếm các ước phân biệt (ví dụ: 12 = 2^2 * 3 có 2 ước nguyên tố phân biệt, không phải 3).