Hiểu bài toán

Bài toán yêu cầu kiểm tra xem một số nguyên dương N có phải là số chính phương đặc biệt hay không. Cụ thể, N được coi là 'số đặc biệt' nếu nó là bình phương của một số nguyên tố. Ta cần đọc số N từ file input và in ra 1 nếu N là bình phương của một số nguyên tố, ngược lại in ra 0.

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

Cách Đếm ước số (Dựa vào số lượng ước)

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

int main() {
 freopen("SOHOC.inp", "r", stdin);
 freopen("SOHOC.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0); 
    int n ; cin >> n ; 
    int d = 0 ;
    for(int i = 1 ; i <= n ; i++ ){
         if ( n % i ==0 ) d++;
    } 
    if (d == 3 ) { 
      cout << "1" ; } else { 
        cout <<"0"; } 
    return 0;

}

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

Phương pháp này dựa trên một tính chất số học: Một số N là bình phương của một số nguyên tố p (tức N = p^2) khi và chỉ khi N có đúng 3 ước số (1, p, và p^2). Do đó, giải pháp là đếm tổng số ước của N. Nếu số ước bằng 3, in ra 1; ngược lại in ra 0. Đây là cách tiếp cận đơn giản nhất về mặt logic, nhưng hiệu năng rất thấp do duyệt toàn bộ khoảng từ 1 đến N.

Cách Kiểm tra bình phương và nguyên tố

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

bool isPrime(long long x) {
    if (x < 2) return false;
    if (x % 2 == 0) return x == 2;
    for (long long i = 3; i * i <= x; i += 2)
        if (x % i == 0) return false;
    return true;
}

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

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

    long long n;
    cin >> n;

    long long p = sqrt(n);
    if (p * p == n && isPrime(p)) cout << 1;
    else cout << 0;

    return 0;
}

• Time Complexity: O(sqrt(N))
• Space Complexity: O(1)

Đây là phương pháp tối ưu và chính xác. Thuật toán thực hiện các bước sau:

1. Tính根 (square root) của N, gọi là p.
2. Kiểm tra xem p có phải là số nguyên không (bằng cách so sánh p*p với N).
3. Nếu p là số nguyên, kiểm tra xem p có phải là số nguyên tố hay không. Nếu cả hai điều kiện trên đều đúng, N là bình phương của số nguyên tố và in ra 1.

Cách Tối ưu hóa Kiểm tra nguyên tố

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

bool isPrime(long long x) {
    if (x < 2) return false;
    for (long long i = 2; i * i <= x; i++)
        if (x % i == 0) return false;
    return true;
}
int main() {
    freopen("SOHOC.INP", "r", stdin);
    freopen("SOHOC.OUT", "w", stdout);
    long long n;
    cin >> n;
    long long root = sqrt(n);
    if (root * root == n && isPrime(root)) cout << 1;
    else cout << 0;
}

• Time Complexity: O(sqrt(N))
• Space Complexity: O(1)

Giải pháp này tương tự như Approach 2, nhưng hàm kiểm tra nguyên tố (isPrime) được viết đơn giản hơn một chút (kiểm tra chia hết cho 2 ngay trong vòng lặp chính). Logic vẫn là tìm根, kiểm tra tính nguyên vẹn và tính nguyên tố của根. Đây là cách tiếp cận chuẩn và hiệu quả cho bài toán này.

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

Bài học kinh nghiệm

• Vấn đề có thể được chuyển hóa thành bài toán kiểm tra tính chất của số root (số căn bậc 2 của N) thay vì kiểm tra trực tiếp N.
• Một số là bình phương của số nguyên tố khi và chỉ khi nó có đúng 3 ước số. Tuy nhiên, cách này chỉ hiệu quả với N nhỏ.

Lỗi thường gặp

• Sử dụng kiểu dữ liệu int có thể gây tràn số (overflow) khi tính bình phương hoặc xử lý các số lớn. Nên dùng kiểu long long.
• Đối với hàm kiểm tra nguyên tố, cần kiểm tra các trường hợp đặc biệt (số chẵn, số nhỏ hơn 2) và dừng vòng lặp đúng thời điểm (i * i <= x).