Hiểu bài toán

Bài toán yêu cầu đếm số lượng số nguyên tố $p$ sao cho $p^2$ là ước của số nguyên dương $N$ cho trước. Nói cách khác, ta cần tìm số lượng nguyên tố $p$ mà $p^2$ chia hết $N$. Ví dụ, nếu $N = 72 = 2^3 \times 3^2$, thì $p=2$ ($2^2 \mid 72$) và $p=3$ ($3^2 \mid 72$) đều thỏa mãn, đáp án là 2.

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

Cách Quy hoạch động - Sàng Eratosthenes (Lỗi)

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

long long demSoNguyenTo(long long limit) {
    if (limit < 2) return 0;
    vector<bool> isPrime(limit + 1, true);
    isPrime[0] = false;
    isPrime[1] = false;
    for (long long i = 2; i * i <= limit; i++) {
        if (isPrime[i]) {
            for (long long j = i * i; j <= limit; j += i) {
                isPrime[j] = false;
            }
        }
    }
    long long count = 0;
    for (long long i = 2; i <= limit; i++) {
        if (isPrime[i]) count++;
    }
    return count;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long n;
    cin >> n;
    // Lỗi logic: Hàm này trả về t tổng số số nguyên tố <= limit,
    // nhưng không kiểm tra điều kiện p^2 chia hết N.
    // Ví dụ N=10, limit=3, hàm trả về 2 (2,3) nhưng chỉ 2 thỏa mãn.
    cout << demSoNguyenTo((long long)sqrt(n)) << endl;
    return 0;
}

• Time Complexity: O(\sqrt{N} \log \log \sqrt{N})
• Space Complexity: O(\sqrt{N})

Code này thực hiện sàng Eratosthenes để đếm số nguyên tố. Tuy nhiên, nó chỉ đơn giản tính số lượng số nguyên tố nhỏ hơn hoặc bằng $\sqrt{N}$. Đây là một đáp án sai logic vì nó không kiểm tra xem $p^2$ có thực sự chia hết $N$ hay không. Nó chỉ đúng nếu $N$ có mọi số nguyên tố nhỏ hơn $\sqrt{N}$ trong phân tích thừa số nguyên tố, điều này không bao giờ xảy ra với số lớn.

Cách Brute Force Phân tích thừa số nguyên tố (Lỗi)

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

int main() {
    long long n;
    cin >> n;
    long long count = 0;
    for (long long i = 2; i * i <= n; i++) {
        if (n % (i * i) == 0) {
            // Lỗi: Chỉ kiểm tra chia hết, không kiểm tra i có phải là số nguyên tố
            // Ví dụ N=16, i=4, 4*4=16 chia hết -> sai
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

• Time Complexity: O(\sqrt{N})
• Space Complexity: O(1)

Approach này thử tất cả các số $i$ từ 2 đến $\sqrt{N}$, kiểm tra xem $i^2$ có chia hết $N$ không. Lỗi ở đây là không kiểm tra tính nguyên tố của $i$. Nó sẽ đếm sai các số hợp số có bình phương chia hết $N$. Ví dụ $N=36$, $i=6$ ($6^2=36$) sẽ được đếm vào dù 6 không phải số nguyên tố.

Cách Sàng Eratosthenes kết hợp Phân tích thừa số nguyên tố (Đúng)

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

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

    long long N;
    cin >> N;

    long long M = sqrt(N); // Chỉ cần sàng đến căn bậc 2 của N

    // Bước 1: Sàng Eratosthenes để tìm các số nguyên tố
    vector<bool> isPrime(M + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (long long i = 2; i * i <= M; i++) {
        if (isPrime[i]) {
            for (long long j = i * i; j <= M; j += i)
                isPrime[j] = false;
        }
    }

    // Bước 2: Kiểm tra từng số nguyên tố p
    long long count = 0;
    for (long long p = 2; p <= M; p++) {
        if (isPrime[p]) {
            // Kiểm tra xem p^2 có chia hết N không
            if (N % (p * p) == 0) {
                count++;
            }
        }
    }

    cout << count;
    return 0;
}

• Time Complexity: O(\sqrt{N} \log \log \sqrt{N})
• Space Complexity: O(\sqrt{N})

Đây là giải pháp chính xác.

1. Tính giới hạn sàng $M = \lfloor\sqrt{N}\rfloor$. Vì nếu $p^2 \mid N$ thì $p \le \sqrt{N}$.
2. Sử dụng sàng Eratosthenes để tạo danh sách tất cả các số nguyên tố từ 2 đến $M$.
3. Duyệt qua từng số nguyên tố $p$ trong danh sách, kiểm tra điều kiện $N \pmod{p^2} == 0$. Nếu thỏa mãn thì tăng biến đếm. Độ phức tạp thời gian chủ yếu đến từ việc sàng, khá nhanh cho $N$ lên đến $10^{12}$. Bộ nhớ cần $O(\sqrt{N})$.

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

Bài học kinh nghiệm

• Nếu $p^2$ là ước của $N$ thì $p$ phải nhỏ hơn hoặc bằng $\sqrt{N}$. Điều này giúp giới hạn phạm vi tìm kiếm.
• Phải kết hợp giữa việc sinh các số nguyên tố (sàng) và kiểm tra điều kiện chia hết cụ thể của bài toán.

Lỗi thường gặp

• Nhầm lẫn giữa việc đếm số lượng ước số bình phương của $N$ và đếm số lượng số nguyên tố $p \le \sqrt{N}$. Hai khái niệm này khác nhau.
• Quên kiểm tra tính nguyên tố của $p$ khi chỉ kiểm tra $p^2 \mid N$. Các số hợp số có thể có bình phương chia hết $N$.
• Sử dụng biến số nguyên nhỏ (int) cho các phép tính với $N$ lớn (lên đến $10^{12}$), dẫn đến tràn số.