Truy vấn đếm cặp nguyên tố cùng nhau không có thứ tự từ 1 đến N C++

Cho Q truy vấn, mỗi truy vấn một số N. Đếm số cặp (i, j) với 1 ≤ i ≤ j ≤ N và gcd(i, j) = 1 (nguyên tố cùng nhau).

Ví dụ

N = 5: Các cặp (1,1),(1,2),(1,3),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5) → 10 cặp.

Giải pháp: Hàm Euler Totient φ(n)

φ(n) = số nguyên dương ≤ n nguyên tố cùng nhau với n.

Số cặp (i, j) với i < j ≤ N và gcd(i,j)=1 là Σ_{j=2..N} φ(j).

Thêm các cặp (i, i): chỉ có (1,1) thỏa mãn (vì gcd(i,i)=i).

Tổng cặp không có thứ tự: 1 + Σ_{j=2..N} φ(j) = Σ_{j=1..N} φ(j).

Tiền xử lý Sieve tính φ

• Khởi tạo phi[i] = i.
• Với mỗi số nguyên tố p: phi[p] = p-1, và cho bội k của p: phi[k] = phi[k]/p * (p-1).
• Tính prefix sum ans[n] = Σ_{i=1..n} phi[i].

Chương trình C++

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

const int MAXN = 1000000;
int phi[MAXN + 1];
long long pref[MAXN + 1];

void computePhi() {
    for (int i = 1; i <= MAXN; i++) phi[i] = i;
    for (int p = 2; p <= MAXN; p++) {
        if (phi[p] == p) { // p là số nguyên tố
            phi[p] = p - 1;
            for (int k = 2 * p; k <= MAXN; k += p)
                phi[k] = phi[k] / p * (p - 1);
        }
    }
    for (int i = 1; i <= MAXN; i++)
        pref[i] = pref[i-1] + phi[i];
}

int main() {
    computePhi();
    int Q = 3;
    int query[] = {5, 7, 9};
    for (int i = 0; i < Q; i++)
        cout << "Query " << i+1 << ": " << pref[query[i]] << endl;
    return 0;
}

Kết quả

Query 1: 10
Query 2: 18
Query 3: 28

Độ phức tạp

Tiền xử lý: O(MAXN log log MAXN). Truy vấn: O(1). Rất hiệu quả cho Q lớn.