HDU 5212 Code：容斥原理計算 GCD 配對和

問題轉化

給定數組 a[1..n]（n≤10⁴, a_i≤10⁴），計算
res = Σ Σ gcd(a[i],a[j]) * (gcd(a[i],a[j]) - 1) (mod 10007)。

容斥思路

設 d[g] = 滿足 gcd(x,y)=g 的有序數對 (x,y) 個數。
先求 tot[g] = 數組中是 g 的倍數的元素個數。
則 gcd 為 g 的倍數的數對數 = tot[g]²。
由大到小容斥：
d[g] = tot[g]² − Σ_k≥2 d[k·g]。
最終答案 = Σ d[g] × g × (g−1) (mod 10007)。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int MOD = 10007;
const int MAXA = 10000;

int cnt[MAXA + 1];
int d[MAXA + 1];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n) {
        fill(cnt, cnt + MAXA + 1, 0);
        int mx = 0;
        for (int i = 0, x; i < n; ++i) {
            cin >> x;
            cnt[x]++;
            mx = max(mx, x);
        }
        long long ans = 0;
        for (int g = mx; g >= 1; --g) {
            long long tot = 0;
            for (int k = g; k <= mx; k += g) tot += cnt[k];
            d[g] = (tot * tot) % MOD;
            for (int k = 2 * g; k <= mx; k += g) {
                d[g] = (d[g] - d[k]) % MOD;
            }
            if (d[g] < 0) d[g] += MOD;
            ans = (ans + 1LL * d[g] * g % MOD * (g - 1)) % MOD;
        }
        cout << (ans + MOD) % MOD << '\n';
    }
    return 0;
}

複雜度

O(M log M)，M = max(a_i) ≤ 10⁴，極快。