Hiểu bài toán

Bài toán yêu cầu tính tổng thu nhập trong một khoảng ngày [X, Y] cho nhiều truy vấn. Tuy nhiên, có một quy tắc loại trừ: nếu một ngày có số thứ tự là số nguyên tố, thì số tiền thu nhập của ngày đó (chỉ khi dương) sẽ không được tính vào tổng. Nói cách khác, ta cần tính tổng bình thường nhưng bớt đi các khoản thu nhập dương vào ngày có số thứ tự là số nguyên tố trong khoảng truy vấn. Dữ liệu n, Q ≤ 50000. Ta cần xử lý nhiều truy vấn nhanh chóng.

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

Cách Sử dụng mảng tổng tiền tố (Prefix Sum)

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

const int N = 50005;
int n, q;
int a[N];
long long prefixSum[N];
bool isPrime[N];

// Hàm sàng Eratosthenes để tìm số nguyên tố
void sieve() {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i < N; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < N; j += i)
                isPrime[j] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    sieve();

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // Xây dựng mảng tổng tiền tố
    // Logic: Nếu là số nguyên tố và a[i] > 0, ta coi como 0 (bị loại bỏ)
    // Ngược lại, giữ nguyên a[i]
    for (int i = 1; i <= n; i++) {
        int val = a[i];
        if (isPrime[i] && a[i] > 0) val = 0;
        prefixSum[i] = prefixSum[i-1] + val;
    }

    cin >> q;
    while(q--) {
        int x, y;
        cin >> x >> y;
        cout << prefixSum[y] - prefixSum[x-1] << "\n";
    }
    return 0;
}

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

Phương pháp này là tối ưu nhất cho bài toán này. Ta preprocessing trước:

1. Dùng sàng Eratosthenes để đánh dấu các số nguyên tố trong phạm vi 50000.
2. Xây dựng mảng tổng tiền tố prefixSum dựa trên mảng thu nhập a. Với mỗi chỉ số i, ta kiểm tra: nếu i là số nguyên tố và a[i] > 0, ta bỏ qua giá trị này (cho bằng 0). Ngược lại, cộng a[i] vào tổng.
3. Với mỗi truy vấn [X, Y], kết quả lấy trực tiếp từ prefixSum[y] - prefixSum[x-1]. Độ phức tạp mỗi truy vấn là O(1).

Cách Tách biệt mảng sum và mảng loại trừ (Prefix Sum 2 mảng)

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

const int N = 1e6 + 2;
vector<bool> s(N, true);
int sum[N], sumS[N]; // sum: tổng bình thường, sumS: tổng các giá trị bị loại bỏ

void sieve(){
    s[0] = s[1] = false;
    for(int i = 2; i * i <= N; i++){
        if(s[i]){
            for(int j = i * i; j <= N; j += i){
                s[j] = false;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    sieve();

    int n, x;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> x;
        sum[i] = sum[i - 1] + x; // Tính tổng tiền tố bình thường
        if(s[i] && x > 0){
            sumS[i] = sumS[i - 1] + x; // Chỉ cộng nếu là số nguyên tố và dương
        }else{
            sumS[i] = sumS[i - 1];
        }
    }
    int q, l, r;
    cin >> q;
    while(q--){
        cin >> l >> r;
        // Công thức: Tổng bình thường - Phần bị loại trừ
        cout << (sum[r] - sum[l - 1]) - (sumS[r] - sumS[l - 1]) << "\n";
    }
    return 0;
}

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

Hầu hết các solution đều có logic này. Solution này tách biệt hai quá trình tính tổng:

1. sum[i] lưu tổng thu nhập từ ngày 1 đến ngày i không phân biệt.
2. sumS[i] lưu tổng thu nhập của những ngày là số nguyên tố và có thu nhập dương từ ngày 1 đến ngày i. Kết quả truy vấn sẽ là (Tổng bình thường) - (Tổng phần bị loại trừ). Đây là cách tiếp cận logic rõ ràng và dễ debug.

Cách Xử lý trực tiếp (Truy vấn chậm)

// Pseudo code cho cách tiếp cận Brute Force
#include <iostream>
using namespace std;

int a[50005];
bool isPrime[50005];

void sieve() {
    // ... sieve logic ...
}

int main() {
    // ... input ...
    int q; cin >> q;
    while(q--) {
        int x, y; cin >> x >> y;
        long long ans = 0;
        for (int i = x; i <= y; i++) {
            if (isPrime[i] && a[i] > 0) continue; // Bỏ qua nếu là số nguyên tố và dương
            ans += a[i];
        }
        cout << ans << endl;
    }
}

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

Đây là cách tiếp cận ngây thơ nhất. Với mỗi truy vấn, ta duyệt qua từng ngày từ X đến Y và cộng dồn lại sau khi kiểm tra điều kiện số nguyên tố. Với N=50000 và Q=50000, độ phức tạp là khoảng 2.5 tỷ phép tính, chắc chắn gây ra Time Limit Exceeded (TLE). Cách này chỉ dùng để kiểm tra tính đúng đắn của logic cho các test nhỏ.

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

Bài học kinh nghiệm

• Bài toán có thể biến đổi thành bài toán tổng tiền tố (Prefix Sum) bằng cách preprocessing các giá trị bị loại bỏ.
• Mấu chốt là xử lý đúng điều kiện 'ngày số nguyên tố AND thu nhập dương'. Nếu chỉ là số nguyên tố mà âm thì vẫn cộng vào bình thường.
• Số ngày tối đa 50000, nên có thể dùng mảng static hoặc vector với kích thước cố định.

Lỗi thường gặp

• Lỗi logic khi xử lý điều kiện loại trừ: Ví dụ viết nhầm thành 'hoặc' (OR) thay vì 'và' (AND), hoặc quên mất số âm của ngày nguyên tố vẫn được tính.
• Lỗi truy cập mảng: Mảng isPrime phải có kích thước đủ lớn (ví dụ 50005 hoặc lớn hơn nếu dùng N=1e6 như Solution 1).
• Kiểu dữ liệu: Tổng thu nhập có thể vượt quá giới hạn của int nếu cộng dồn nhiều giá trị dương lớn, nên dùng long long cho mảng prefix sum.