Hiểu bài toán

Cho một dãy số nguyên dương $ai$ với $1 \le n \le 10^4$ và $1 \le ai \le 10^6$. Nhiệm vụ là đếm số lượng cặp chỉ số $(i, j)$ (có thể $i=j$ hoặc không) sao cho $\text{gcd}(ai, aj) = 1$. Nói cách khác, chúng ta cần tìm số cặp số nguyên tố trong dãy.

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

Cách Brute Force

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (gcd(a[i], a[j]) == 1) {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

• Time Complexity: O(n^2 * log(max(A)))
• Space Complexity: O(n)

Đây là cách giải quyết trực tiếp nhất. Duyệt qua tất cả các cặp $(i, j)$ trong dãy, tính $\text{gcd}(ai, aj)$ và kiểm tra xem nó có bằng 1 hay không. Với $n \le 10^4$, số lượng phép tính là $10^8$, mỗi phép tính $\text{gcd}$ mất khoảng $\log(10^6) \approx 20$ thao tác. Tổng cộng khoảng $2 \times 10^9$ thao tác, quá thời gian cho phép (thường là 1 giây). Do đó, phương pháp này không khả thi cho dữ liệu lớn.

Cách Sử dụng Bổ sung Euclid và Tần suất (Hash Map)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> cnt;
    int maxVal = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        cnt[a[i]]++;
        maxVal = max(maxVal, a[i]);
    }

    // Duyệt qua các giá trị duy nhất
    vector<int> distinct_values;
    for (auto p : cnt) distinct_values.push_back(p.first);

    long long ans = 0;
    int m = distinct_values.size();
    for (int i = 0; i < m; i++) {
        int u = distinct_values[i];
        for (int j = 0; j < m; j++) {
            int v = distinct_values[j];
            if (gcd(u, v) == 1) {
                ans += (long long)cnt[u] * cnt[v];
            }
        }
    }
    cout << ans << endl;
    return 0;
}

• Time Complexity: O(M^2 log M) hoặc O(N sqrt(M))
• Space Complexity: O(M)

Phương pháp này tối ưu hóa Brute Force bằng cách gom các số trùng lặp lại. Thay vì duyệt $n^2$ cặp, ta chỉ duyệt qua các cặp giá trị duy nhất (gọi là $M$). Nếu có nhiều số trùng lặp, $M$ sẽ nhỏ hơn $n$ rất nhiều. Tuy nhiên, trong trường hợp xấu nhất (tất cả các số đều khác nhau), độ phức tạp vẫn là $O(N^2)$. Với $N=10^4$, $M=10^4$, độ phức tạp khoảng $10^8$ lại một lần nữa, có thể chạy đúng trong C++ nếu tối ưu tốt nhưng rủi ro tràn số rất cao (nếu $N=10^4$ và tất cả đều nguyên tố cùng nhau, kết quả là $10^8$, vừa vặn trong long long nhưng thời gian chạy có thể vượt quá giới hạn).

Cách Sử dụng Hàm Số Euler và Bổ sung Inclusion-Exclusion

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

const int MAXA = 1000000;
int mu[MAXA + 1];
bool isComp[MAXA + 1];
vector<int> primes;

void mobiusSieve() {
    mu[1] = 1;
    for (int i = 2; i <= MAXA; i++) {
        if (!isComp[i]) {
            primes.push_back(i);
            mu[i] = -1;
        }
        for (int p : primes) {
            if (1LL * i * p > MAXA) break;
            isComp[i * p] = true;
            if (i % p == 0) {
                mu[i * p] = 0;
                break;
            } else {
                mu[i * p] = -mu[i];
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    mobiusSieve();

    int n;
    cin >> n;
    vector<int> freq(MAXA + 1, 0);
    int maxVal = 0;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        freq[x]++;
        maxVal = max(maxVal, x);
    }

    vector<long long> cnt(MAXA + 1, 0);
    // cnt[d] là số lượng số trong dãy chia hết cho d
    for (int d = 1; d <= maxVal; d++) {
        for (int j = d; j <= maxVal; j += d) {
            cnt[d] += freq[j];
        }
    }

    long long ans = 0;
    for (int d = 1; d <= maxVal; d++) {
        if (mu[d] == 0) continue;
        // Sử dụng công thức: tổng_{d} mu[d] * (số cặp chia hết cho d)^2
        ans += mu[d] * cnt[d] * cnt[d];
    }

    cout << ans << endl;
    return 0;
}

• Time Complexity: O(MAXA log log MAXA)
• Space Complexity: O(MAXA)

Đây là phương pháp tối ưu nhất, sử dụng Bổ sung Inclusion-Exclusion kết hợp với Hàm số Mobius (hoặc cách tiếp cận tương tự dựa trên tính chất của số nguyên tố).

1. Tính tần suất xuất hiện của mỗi số.
2. Tính $cnt[d]$: số lượng các số trong dãy chia hết cho $d$. Điều này có thể làm bằng cách duyệt bội số của $d$. Độ phức tạp là $O(MAXA \log MAXA)$.
3. Sử dụng công thức: Số cặp $(i, j)$ sao cho $\text{gcd}(ai, aj) = 1$ là: $$ \sum_{d=1}^{MAXA} \mu(d) \cdot cnt[d]^2 $$ Trong đó $\mu(d)$ là hàm số Mobius. $\mu(d) = 1$ nếu $d$ là tích của một số nguyên tố mũ lẻ các số khác nhau, $-1$ nếu tích của một số nguyên tố mũ chẵn, và $0$ nếu chứa bình phương của một số nguyên tố. Công thức này đếm tổng số cặp chia hết cho $d$ và hiệu chỉnh lại bằng dấu cộng/trừ để chỉ còn lại các cặp nguyên tố cùng nhau. Độ phức tạp chủ yếu ở bước tính $cnt[d]$, rơi vào khoảng $10^6 \times 14 \approx 1.4 \times 10^7$ thao tác, hoàn toàn chấp nhận được.

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

Bài học kinh nghiệm

• Bài toán đếm số cặp có ước chung bằng 1 có thể quyمواقف về bài toán tổng hợp các cặp có ước chung là bội của $d$ với hệ số Mobius.
• Sử dụng Bổ sung Inclusion-Exclusion (Quy tắc loại trừ) là chìa khóa để giải quyết bài toán này trong thời gian hiệu quả thay vì duyệt trực tiếp tất cả các cặp.
• Hàm số Mobius (Mobius function) giúp tính toán các hệ số trong công thức Bổ sung một cách chính xác.

Lỗi thường gặp

• Làm sai công thức tính tổng số cặp có ước chung bằng 1 nếu không hiểu rõ ý nghĩa của $\mu(d)$.
• Quên dùng long long cho biến kết quả vì số cặp có thể lên tới $10^8$.
• Trong cách tiếp cận thứ 2 (Hash Map), nếu không tối ưu tốt vòng lặp hoặc số lượng phần tử duy nhất quá lớn ($10^4$), độ phức tạp có thể trở thành $O(N^2)$ và bị TLE.
• Xử lý sai trường hợp số 1 trong hàm Mobius hoặc các số có bình phương thừa số nguyên tố.