Hiểu bài toán

Bài toán yêu cầu đếm số lượng xe có biển số nguyên tố. Tuy nhiên, đầu vào là các biển số đã bị hệ thống nhận dạng đảo ngược. Ví dụ: biển số gốc '0003' (số 3) thì bị nhận dạng thành '3000'. Để giải quyết, ta cần thực hiện các bước sau:

1. Đọc vào N biển số đã bị đảo ngược (dạng chuỗi 4 ký tự).
2. Với mỗi biển số, thực hiện đảo ngược lại chuỗi đó để lấy được biển số gốc.
3. Chuyển chuỗi biển số gốc thành số nguyên.
4. Kiểm tra xem số đó có phải là số nguyên tố không.
5. Đếm và in ra tổng số xe thỏa mãn.

Lưu ý: Biển số xe có thể có số 0 ở đầu (ví dụ '0013'), nên việc xử lý chuỗi là bắt buộc thay vì chỉ xử lý số nguyên.

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

Cách Xử lý số học (Math)

#include <bits/stdc++.h>
using namespace std;
long long isPrime(long long n) {
    if (n < 2){ return 0;}else{
    for (long long i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return 0;
    }
    }
    return 1;
}
long long a[1000011],n,s=0;
int main()
{
    cin >> n;
    for(long long i=0;i<n;i++){
            cin >> a[i];
    }
    for(long long i=0;i<n;i++){
            long long x=a[i]%10;
            long long y=(a[i]/10)%10;
            long long z=(a[i]/100)%10;
            long long b=(a[i]/1000)%10;
            long long skibidi=x*1000+y*100+z*10+b;
            if(isPrime(skibidi)){
                    s++;
            }
    }
    cout << s;
    return 0;
}

• Time Complexity: O(N * sqrt(M))
• Space Complexity: O(N)

Cách tiếp cận này sử dụng các phép toán số học (chia lấy dư) để tách từng chữ số của biển số đã nhập. Nó lấy chữ số hàng đơn vị, chục, trăm, nghìn rồi ráp lại theo thứ tự ngược lại để tạo ra số nguyên tố gốc. Hàm kiểm tra nguyên tố được cài đặt trực quan bằng vòng lặp từ 2 đến căn bậc hai của số đó. Ưu điểm: Trực tiếp thao tác trên số, không cần chuyển đổi qua string. Nhược điểm: Xử lý số 0 ở đầu hơi rủi ro nếu nhập vào dưới dạng số nguyên (ví dụ '0870' có thể được đọc là 870 nếu dùng cin >> int). Tuy nhiên trong code này, mảng a khai báo là long long nên có thể chứa giá trị, nhưng logic đảo số x*1000 + ... sẽ sai nếu giá trị nhập vào bị mất số 0 đầu (ví dụ nhập 870 thay vì 0870).

Cách Xử lý Chuỗi và Kiểm tra Lặp

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define task ""

void pre () {
    freopen(task".inp", "r", stdin);
    freopen(task".out", "w", stdout);
}
/*_______________________SOLUTION IS HERE____________________________________*/

bool check (int x) {
    for (int i = 2; i <= sqrt(x); ++i)
        if (x % i == 0) return false;
    return x > 1;
}


int n, d = 0;
signed  main() {
    //pre();
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int c;
        cin >> c;
        string res = to_string(c);
        reverse(res.begin(), res.end());
        if (check(stoi(res + string(4 - res.size(), '0')))) ++d;
    }
    cout << d;
    return 0;
}

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

Cách tiếp cận này đọc dữ liệu dưới dạng số nguyên, sau đó chuyển đổi thành chuỗi để xử lý. Bước 1: Đọc số c. Bước 2: Chuyển c thành chuỗi res. Bước 3: Đảo ngược chuỗi res. Bước 4:补齐 chuỗi: Vì biển số có 4 chữ số, biển số '0001' khi đọc là số 1 sẽ thành chuỗi "1". Sau khi đảo ngược vẫn là "1". Ta cần nối thêm các ký tự '0' vào cuối chuỗi cho đủ 4 ký tự (vì biển số gốc là 4 chữ số). Code dùng string(4 - res.size(), '0') để tạo chuỗi '0' và nối vào. Bước 5: Chuyển chuỗi đã补齐 về số nguyên và kiểm tra nguyên tố. Cách này xử lý đúng các trường hợp số 0 ở đầu bằng cách dùng chuỗi.

Cách Sàng Nguyên Tố (Precomputation)

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

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

int main() {
    int n;
    cin >> n; // số lượng xe
    vector<bool> prime(10000, false);

    // sàng số nguyên tố từ 1 đến 9999
    for(int i = 1; i <= 9999; i++){
        if(isPrime(i)) prime[i] = true;
    }

    int count = 0;
    for(int i = 0; i < n; i++){
        string s;
        cin >> s; // đọc biển số dạng 4 ký tự
        reverse(s.begin(), s.end()); // đảo ngược chuỗi
        int rev = stoi(s);           // chuyển sang số nguyên
        if(prime[rev]) count++;
    }

    cout << count << endl;
    return 0;
}

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

Đây là cách tiếp cận tối ưu nhất. Bước 1: Tạo một mảng đánh dấu (sieve) cho các số từ 1 đến 9999. Ta chỉ cần chạy hàm kiểm tra nguyên tố một lần cho các số trong khoảng này. Bước 2: Đọc dữ liệu trực tiếp dưới dạng chuỗi s. Điều này đảm bảo ta giữ được các số 0 ở đầu. Bước 3: Đảo ngược chuỗi s. Bước 4: Chuyển chuỗi thành số nguyên rev (không cần补齐 vì stoi tự xử lý). Bước 5: Kiểm tra prime[rev] trong mảng đã sàng. Nếu true thì tăng biến đếm. Phương pháp này rất nhanh vì việc kiểm tra nguyên tố chỉ là truy cập mảng O(1), phù hợp với giới hạn N=50000.

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

Bài học kinh nghiệm

• Biển số xe luôn có 4 chữ số, có thể bao gồm các số 0 ở đầu. Do đó, việc xử lý dữ liệu đầu vào dưới dạng chuỗi là an toàn và chính xác nhất.
• Thao tác đảo ngược chuỗi là trung tâm của bài toán: '3000' -> '0003'.
• Vì giá trị biển số chỉ nằm trong khoảng 0000 đến 9999, ta có thể tiền xử lý (precompute) danh sách số nguyên tố trong khoảng này để tăng tốc độ kiểm tra.

Lỗi thường gặp

• Đọc dữ liệu dưới dạng số nguyên (int) và cho rằng giá trị 0001 sẽ được lưu trữ là '1'. Nếu dùng phép toán số học trực tiếp mà không补齐 số 0, ta sẽ tính toán sai giá trị biển số gốc.
• Quên kiểm tra số 1 hoặc số 0 không phải là số nguyên tố.
• Sử dụng stoi trên chuỗi "0003" sẽ trả về 3, điều này không sai, nhưng cần đảm bảo chuỗi đầu vào được xử lý đúng trước khi đảo ngược.