Hiểu bài toán

Bài toán yêu cầu đếm các số nguyên tố lũy thừa (T-Prime). Một số được gọi là T-Prime nếu nó có đúng ba ước số nguyên dương. Qua phân tích, ta thấy rằng một số nguyên dương có đúng ba ước khi và chỉ khi nó là bình phương của một số nguyên tố. Ví dụ: 4 ($2^2$) có các ước là 1, 2, 4 (đúng 3 ước). Do đó, bài toán quy về việc kiểm tra xem số $x$ có phải là bình phương của một số nguyên tố hay không. Dải giá trị của $x$: $1 \le x \le 10^{12}$. Dải giá trị của $n$ (số lượng test cases) khá lớn, cần xử lý hiệu quả.

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

Cách Hash Set loại trừ trùng lặp (Optimized Naive)

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

const int MAXP = 1000000; // sqrt(1e12)

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("TPRIME.INP", "r", stdin);
    freopen("TPRIME.OUT", "w", stdout);

    int n;
    cin >> n;
    vector<long long> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    // Sàng Eratosthenes
    vector<bool> isPrime(MAXP+1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i*i <= MAXP; i++) {
        if (isPrime[i]) {
            for (int j = i*i; j <= MAXP; j += i)
                isPrime[j] = false;
        }
    }

    int countTPrime = 0;
    unordered_set<long long> seen; // tránh đếm trùng

    for (long long x : arr) {
        if (seen.count(x)) continue; // bỏ qua nếu đã đếm
        long long p = sqrtl(x);
        if (p * p == x && isPrime[p]) {
            countTPrime++;
            seen.insert(x);
        }
    }

    cout << countTPrime;
    return 0;
}

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

Cách tiếp cận này xử lý từng số đầu vào một. Với mỗi số $x$, ta tính căn bậc hai nguyên $p = \sqrt{x}$. Nếu $p^2 = x$ (tức $x$ là số chính phương) và $p$ là số nguyên tố (kiểm tra qua mảng đã sàng), thì $x$ là T-Prime. Để tránh đếm trùng các số T-Prime xuất hiện nhiều lần trong danh sách đầu vào, ta sử dụng một unordered_set. Phức tạp sàng nguyên tố là $O(10^6 \log \log 10^6)$, khá nhanh. Phức tạp xử lý $N$ số là $O(N)$.

Cách Sàng Eratosthenes truyền thống

#include <bits/stdc++.h>
#define ll long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
using namespace std;

const int MAX = 1e6 + 1; 

int p[MAX];

void sang() {
    FOR(i, 1, MAX) p[i] = 1;
    p[0] = p[1] = 0;
    for (int i = 2; i * i <= MAX; i++) {
        if (p[i]) {
            for (int j = i * i; j <= MAX; j += i) p[j] = 0;
        }
    }
}

bool check(ll x) {
    ll sq = sqrt(x);
    return (sq * sq == x && p[sq]);
}

int main() {
    freopen("tprime.inp","r", stdin);
    freopen("tprime.out", "w", stdout);
    ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL); 
    sang();
    int n; cin >> n;
    set<int> se;
    FOR(i, 1, n) {
        ll x; cin >> x;
        if (check(x)) se.insert(x);
    }
    cout << se.size();
    return 0;
}

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

Đây là cách tiếp cận cơ bản nhất. Tạo một mảng boolean p để lưu trạng thái nguyên tố của các số đến $10^6$. Với mỗi số đầu vào, kiểm tra xem nó có phải là bình phương của một số nguyên tố hay không bằng hàm check. Sử dụng set<int> để lưu trữ các T-Prime duy nhất và in ra kích thước của set. set cho độ phức tạp $O(\log N)$ cho mỗi thao tác chèn. So với cách dùng hash set, cách này chậm hơn một chút ở phần xử lý đầu vào nhưng logic tương đối rõ ràng.

Cách Binary Search (Tham khảo)

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

const int MAX = 1e6 + 1;
bool isPrime[MAX];
vector<int> primes;

void sieve() {
    fill(isPrime, isPrime + MAX, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i < MAX; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
            if (1LL * i * i < MAX)
                for (int j = i * i; j < MAX; j += i)
                    isPrime[j] = false;
        }
    }
}

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

    int n;
    if (cin >> n) {
        int count = 0;
        while (n--) {
            long long x;
            cin >> x;
            long long root = sqrt(x);
            if (root * root == x && binary_search(primes.begin(), primes.end(), (int)root)) {
                count++;
            }
        }
        cout << count;
    }
    return 0;
}

• Time Complexity: O(N log log MAX)
• Space Complexity: O(MAX)

Thay vì kiểm tra mảng boolean, ta có thể lưu các số nguyên tố vào một vector primes và sử dụng binary_search để kiểm tra. Đây là một cách thay thế cho việc truy cập mảng trực tiếp. Tuy nhiên, so với việc truy cập mảng boolean $O(1)$, việc dùng binary search sẽ tốn $O(\log(\pi(MAX)))$ ~ $O(\log(10^5))$, vẫn rất nhanh nhưng không tối ưu bằng cách Hash Map/Boolean Array.

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

Bài học kinh nghiệm

• Một số có đúng 3 ước số khi và chỉ khi nó là bình phương của một số nguyên tố.
• Với $x \le 10^{12}$, căn bậc hai của $x$ tối đa là $10^6$. Do đó, chỉ cần sàng nguyên tố đến $10^6$.
• Sử dụng unordered_set hoặc set để loại bỏ các số T-Prime trùng lặp trong danh sách đầu vào.

Lỗi thường gặp

• Sai kiểu dữ liệu: $x$ có thể lên tới $10^{12}$, phải dùng long long (hoặc unsigned long long).
• Lỗi tính căn bậc hai: sqrt(x) trả về số thực, có thể sai do làm tròn. Cần kiểm tra lại bằng cách tính sqrt(x) -> long long rồi nhân ra để so sánh.
• Quên kiểm tra điều kiện $x$ phải là số chính phương trước khi kiểm tra tính nguyên tố của căn.
• Sử dụng cin/cout không tắt đồng bộ hóa I/O có thể gây trễ khi xử lý lượng lớn dữ liệu.