Hiểu bài toán

Bài toán yêu cầu đếm số lượng số nguyên tố trong các đoạn của một dãy số A. Dãy số A được tạo ra công thức a_i = (p * i) mod m + q với i từ 1 đến N. Với T truy vấn, mỗi truy vấn yêu cầu đếm số lượng số nguyên tố trong đoạn từ chỉ số u đến v của dãy A. Kích thước N và T có thể lên đến 10^5, nhưng các giá trị p, q, m chỉ lên đến 10^6.

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

Cách Brute Force với sàng số nguyên tố

#include <bits/stdc++.h>

using namespace std;
static int b[2000001];
int a[1000000];
int main()
{
    int n,t;
    cin>>n>>t;
    int p,q,m;
    cin>>p>>q>>m;
    for(int i=1;i<=n;i++)
    {
        a[i]=p*i%m+q;
    }
    b[1]=1;
    for(int i=2;i*i<=2000001;i++)
    {
        if(b[i]==0)
            for(int j=i*2;j<=2000001;j+=i)
        {
            b[j]=1;
        }
    }
    int u,v;
    int dem=0;
    for(int i=1;i<=t;i++)
    {
        dem=0;
        cin>>u>>v;
        for(int j=u;j<=v;j++)
        {
            if(b[a[j]]==0)dem++;
        }
        cout<<dem<<endl;
    }
    return 0;
}

• Time Complexity: O(T * N)
• Space Complexity: O(N + V)

Phương pháp này xử lý từng truy vấn một cách độc lập. Trước tiên, ta tạo ra dãy A và dùng sàng Eratosthenes để đánh dấu các số không nguyên tố trong phạm vi giá trị tối đa có thể của A (khoảng 210^6). Với mỗi truy vấn (u, v), ta duyệt từ u đến v và đếm các phần tử là số nguyên tố bằng cách tra mảng đánh dấu. Do mỗi truy vấn duyệt qua tối đa N phần tử và có T truy vấn, độ phức tạp thời gian là O(TN).

Cách Tiền xử lý mảng tiền tố (Prefix Sum)

#include<bits/stdc++.h>
#define ll long long
const ll N = 2e5+5;
const ll MAXN = 1e6+5;
using namespace std;
ll p, q, mod, n, t;
ll qk[N] = {};
ll ck[N] = {};

ll prime(ll x) {
    if (x < 2) return 0;
    for (ll i=2; i*i<=x; ++i) 
        if (x % i == 0) return 0;
    return 1;
}

ll query(ll x, ll y) {
    return ck[y] - ck[x-1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> t;
    cin >> p >> q >> mod;

    // Tạo dãy A và mảng tiền tố
    for (ll i=1; i<=n; ++i) {
        qk[i] = (p % mod) * (i % mod) % mod + q;
        if (prime(qk[i])) {
            ck[i] = ck[i-1] + 1;
        } else {
            ck[i] = ck[i-1];
        }
    }

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

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

Thay vì duyệt lại mỗi truy vấn, ta tiền xử lý một mảng phụ 'ck' trong đó ck[i] là số lượng số nguyên tố từ a1 đến ai. Cách tiếp cận này trong code mẫu sử dụng hàm prime(n) để kiểm tra tính nguyên tố mỗi phần tử khi tạo mảng tiền tố. Độ phức tạp tạo mảng tiền tố là O(N * sqrt(V)) do mỗi phần tử mất O(sqrt(V)) để kiểm tra. Tuy nhiên, trả lời truy vấn chỉ mất O(1) bằng cách lấy hiệu ck[v] - ck[u-1].

Cách Tối ưu với Sàng Eratosthenes và Mảng tiền tố

#include <bits/stdc++.h>
using namespace std;
const int MAX = 2000005;
const int MAXN = 1000005;

int p, q, mod, n, t;
int a[MAXN];
int pref[MAXN];
bool is_composite[MAX];

void sieve() {
    is_composite[0] = is_composite[1] = true;
    for (int i = 2; i * i < MAX; i++) {
        if (!is_composite[i]) {
            for (int j = i * i; j < MAX; j += i)
                is_composite[j] = true;
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> t;
    cin >> p >> q >> mod;

    sieve();

    // Tạo dãy A và mảng tiền tố
    for (int i = 1; i <= n; i++) {
        a[i] = (1LL * p * i) % mod + q;
        pref[i] = pref[i-1] + (!is_composite[a[i]]);
    }

    while (t--) {
        int u, v;
        cin >> u >> v;
        cout << pref[v] - pref[u-1] << "\n";
    }
    return 0;
}

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

Đây là cách tiếp cận tối ưu nhất. Ta dùng sàng Eratosthenes (Sieve) để preprocess các số nguyên tố trong phạm vi tối đa (khoảng 2.000.000 vì p, q, m <= 10^6). Sau đó, ta tạo mảng tiền tố 'pref' chỉ trong một lượt duyệt O(N). Mỗi truy vấn được trả lời ngay lập tức với độ phức tạp O(1).

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

Bài học kinh nghiệm

• Giá trị của phần tử a_i bị giới hạn bởi p + q + m (tối đa khoảng 2*10^6), cho phép ta sử dụng sàng Eratosthenes để kiểm tra tính nguyên tố trong phạm vi này.
• Bài toán đếm trong đoạn liên tiếp (range query) có thể được tối ưu hóa bằng cách tiền xử lý mảng tiền tố (prefix sum array).
• Kiểm tra tính nguyên tố bằng vòng lặp sqrt(x) chỉ phù hợp khi số lượng phần tử cần kiểm tra ít hoặc giá trị x nhỏ.

Lỗi thường gặp

• Overkill trong brute force: Dùng vòng lặp kiểm tra nguyên tố lặp lại cho mỗi phần tử trong mỗi truy vấn sẽ bị TLE.
• Sai kiểu dữ liệu: Khi nhân p * i có thể vượt quá giới hạn của int (2*10^9), cần dùng long long hoặc ép kiểu trước khi tính toán.
• Quên xử lý số 1: Số 1 không phải là số nguyên tố.
• Lỗi truy cập mảng: Mảng a có kích thước N, nhưng giá trị a[i] dùng để truy cập mảng sieve phải nằm trong kích thước bộ nhớ mảng sieve (phải đủ lớn để chứa giá trị lớn nhất của a[i]).