Hiểu bài toán

Bài toán yêu cầu đếm số lượng số nguyên dương trong một ma trận M x N có đặc điểm sau: số đảo ngược của nó (đọc từ phải sang trái) phải là một số nguyên tố. Ví dụ, với số 31, số đảo ngược là 13 (số nguyên tố), do đó 31 được đếm. Với số 12, số đảo ngược là 21 (không phải số nguyên tố), nên không được đếm. Nhập vào từ file TIMSO.INP gồm M, N và ma trận các số nguyên dương. Xuất ra file TIMSO.OUT số lượng số thỏa mãn.

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

Cách Brute Force (Tối ưu hóa)

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

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

int reverseNumber(int x) {
    int y=0;
    while (x>0){
        y = y*10 + x%10;
        x/=10;
    }
    return y;
}

int main() {
    ifstream fin("TIMSO.INP");
    ofstream fout("TIMSO.OUT");

    int M,N;
    fin >> M >> N;
    int count=0;
    for(int i=0;i<M;i++){
        for(int j=0;j<N;j++){
            int x;
            fin >> x;
            int y = reverseNumber(x);
            if (isPrime(y)) count++;
        }
    }

    fout << count << "\n";
    return 0;
}

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

Đây là cách tiếp cận trực tiếp nhất. Với mỗi phần tử trong ma trận, ta thực hiện hai thao tác: (1) Đảo ngược số để lấy giá trị y. (2) Kiểm tra xem y có phải là số nguyên tố không bằng cách lặp từ 2 đến căn bậc hai của y. Độ phức tạp thời gian phụ thuộc vào giá trị lớn nhất của các số trong ma trận.

Cách Xử lý số lớn (Long Long)

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

long long rev_num(long long x){
    long long r = 0;
    while (x > 0){
        r = r * 10 + x % 10;
        x /= 10;
    }
    return r;
}

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("timso.inp","r",stdin);
    freopen("timso.out","w",stdout);

    int M, N;
    cin >> M >> N;

    int cnt = 0;
    long long x;

    for(int i = 0; i < M; i++){
        for(int j = 0; j < N; j++){
            cin >> x;
            long long y = rev_num(x);
            if (isPrime(y)) cnt++;
        }
    }

    cout << cnt;
    return 0;
}

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

Các giải pháp được chấp nhận đều sử dụng kiểu dữ liệu long long cho các số đầu vào. Điều này cho thấy các số trong bài toán có thể lớn hơn int (ví dụ: 10^9 hoặc hơn). Việc sử dụng long long đảm bảo không bị tràn số khi lưu trữ hoặc đảo ngược các số lớn. Logic tính toán vẫn giữ nguyên như cách tiếp cận đầu tiên.

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

Bài học kinh nghiệm

• Bài toán là kết hợp của hai bài toán con độc lập: Đảo số và Kiểm tra số nguyên tố.
• Các số đầu vào có thể nằm ngoài phạm vi 32-bit thông thường, nên cần sử dụng long long để đảm bảo an toàn.
• Việc kiểm tra số nguyên tố chỉ cần lặp đến căn bậc hai của số đó (sqrt(n)), giúp giảm đáng kể thời gian thực thi so với việc lặp đến n-1.

Lỗi thường gặp

• Sử dụng int thay cho long long có thể gây tràn số (overflow) khi các số đầu vào lớn.
• Quên kiểm tra các trường hợp đặc biệt của số nguyên tố như số 2 (số chẵn duy nhất là nguyên tố) hoặc các số nhỏ hơn 2.
• Đọc sai định dạng input hoặc không đóng file input/output đúng cách (trong C++ ifstream/ofstream).