Hiểu bài toán

Bài toán yêu cầu xử lý nhiều truy vấn. Với mỗi truy vấn, cho hai số nguyên dương L và R (trong bài là r và l). Nhiệm vụ là tìm tổng tất cả các số nguyên tố trong khoảng [L, R] mà đồng thời là số đối xứng (số palindrome). Số đối xứng là số mà khi đọc từ trái sang phải giống hệt đọc từ phải sang trái (ví dụ: 121, 1331). Input bao gồm số lượng truy vấn Q, sau đó Q dòng mỗi dòng chứa L và R. Output là tổng các số thỏa mãn điều kiện cho mỗi truy vấn.

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

Cách Brute Force

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

// Kiểm tra số đối xứng
bool check(string s) {
    int n = s.length();
    for(int i = 0; i < n/2; i++) {
        if (s[i] != s[n-i-1]) return false;
    }
    return true;
}

// Kiểm tra số nguyên tố
bool isPrime(unsigned long long n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (unsigned long long i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

int main() {
    int q; cin >> q;
    while(q--) {
        ll ans = 0;
        int r, l; cin >> r >> l;
        // Duyệt qua từng số trong đoạn [r, l]
        for(int i = r; i <= l; i++) {
            if (isPrime(i)) {
                string str = to_string(i);
                if (check(str)) {
                    ans += i;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

• Time Complexity: O(Q * (R - L) * sqrt(R))
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp nhất (Naive). Với mỗi truy vấn, ta duyệt qua từng số i từ L đến R. Với mỗi số, ta kiểm tra xem nó có phải là số nguyên tố không (dùng vòng lặp jusqu sqrt(n)), và kiểm tra xem nó có phải là số đối xứng không (bằng cách chuyển sang string và so sánh ký tự). Nếu cả hai điều kiện đều thỏa mãn, cộng i vào tổng.

Ưu điểm: Dễ hiểu, dễ cài đặt. Nhược điểm: Rất chậm do phải lặp lại việc kiểm tra nguyên tố cho mỗi số trong mỗi truy vấn. Nếu khoảng cách R - L lớn, độ phức tạp sẽ rất cao.

Cách Precomputation (Tính toán trước)

#include <bits/stdc++.h>
#define ll long long
const ll N = 2e5+5;
using namespace std;
ll a[N] = {};

// Kiểm tra số nguyên tố (Optimized)
bool prime(ll x) {
    if (x < 2) return false;
    for (ll i = 2; i <= sqrt(x); ++i)
        if (x % i == 0) return false;
    return true;
}

// Kiểm tra số đối xứng
bool nguoc(ll x) {
    string s = to_string(x);
    string t = s;
    reverse(t.begin(), t.end());
    return s == t;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // Tăng giới hạn bộ nhớ đệm nếu cần, ở đây dùng mảng a[N]
    // Giả sử N đủ lớn để chứa giá trị max của R

    // Bước 1: Tạo mảng tổng tiền tố (Prefix Sum)
    for (ll i = 2; i < N; ++i) {
        if (prime(i) && nguoc(i)) {
            a[i] = i;
        }
    }

    // Bước 2: Tính tổng tiền tố
    for (ll i = 1; i < N; ++i) a[i] += a[i-1];

    ll t, x, y;
    cin >> t;
    while (t--) {
        cin >> x >> y;
        // Trả lời truy vấn O(1)
        cout << a[y] - a[x-1] << endl;
    }
    return 0;
}

• Time Complexity: O(N * sqrt(N) + Q)
• Space Complexity: O(N)

Phương pháp này tối ưu hóa bằng cách tách biệt quá trình tính toán và trả lời truy vấn.

1. Tiền xử lý (Precomputation): Ta xác định một giới hạn tối đa có thể có của R (ví dụ trong code là 200,000 hoặc 100,000). Ta duyệt từ 1 đến giới hạn này, tạo một mảng a trong đó a[i] bằng i nếu i là số nguyên tố đối xứng, và bằng 0 nếu không.
2. Tổng tiền tố (Prefix Sum): Sau đó ta biến đổi mảng a thành mảng tổng tiền tố, sao cho a[i] lưu tổng tất cả các số thỏa mãn từ 1 đến i.
3. Trả lời truy vấn: Với mỗi truy vấn [L, R], kết quả chỉ cần lấy a[R] - a[L-1]. Việc này thực hiện trong thời gian hằng số O(1).

Ưu điểm: Rất nhanh cho các truy vấn. Nhược điểm: Chỉ hiệu quả nếu các giá trị L, R bị giới hạn trong một phạm vi nhỏ (ví dụ < 200,000). Nếu R có thể lên tới 10^9, mảng sẽ không đủ bộ nhớ.

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

Bài học kinh nghiệm

• Bài toán có thể chia làm 2 giai đoạn: tiền xử lý dữ liệu và trả lời truy vấn.
• Sử dụng kỹ thuật Prefix Sum (Tổng tiền tố) biến truy vấn tổng trong đoạn [L, R] thành thao tác trừ đơn giản O(1).
• Số đối xứng (palindrome) có mật độ khá thưa trong các số tự nhiên, kết hợp với điều kiện nguyên tố càng làm số lượng số cần xét giảm đi đáng kể.

Lỗi thường gặp

• Lỗi tràn số (Integer Overflow): Tổng các số có thể rất lớn, cần dùng kiểu dữ liệu 64-bit (long long).
• Quên kiểm tra biên khi tính tổng tiền tố (ví dụ truy cập a[x-1] khi x=1, cần xử lý mảng từ chỉ số 1 hoặc kiểm tra điều kiện).
• Hiệu năng kiểm tra nguyên tố: Kiểm tra bằng vòng lặp đến n-1 là quá chậm, phải tối ưu đến sqrt(n) hoặc dùng sàng Eratosthenes.
• Giả sử sai về giới hạn input: Solution 1 và 3 chạy chậm do duyệt lại từ đầu với mỗi truy vấn, phù hợp khi R-L nhỏ. Solution 2 chạy nhanh O(1) nhưng cần biết trước giới hạn tối đa của R để khai báo mảng.