NOJ 2079 Prime：莫比烏斯反演計算互質對數

問題描述

給定 n 個整數（≤10^5），求其中互質數對（gcd=1）的個數。多測試用例，n≤10^5。

數學建模：容斥原理與莫比烏斯函數

總數對 = C(n,2)。需減去 gcd>1 的數對。設 num[d] 為能被 d 整除的元素個數，則 gcd 為 d 的倍數的數對數為 C(num[d],2)。由容斥：

答案 = Σ_{d=1}^{max} μ(d) * C(num[d], 2)

其中 μ 為莫比烏斯函數：μ(1)=1；質因數個數為偶數 μ=1，奇數 μ=-1；含平方因子 μ=0。

線性篩預計算 μ 函數

void Mobius() {
    mob[1] = 1;
    for (int i = 2; i < MAX; ++i) {
        if (prime[i]) { p[pnum++] = i; mob[i] = -1; }
        for (int j = 0; j < pnum && i * p[j] < MAX; ++j) {
            prime[i * p[j]] = false;
            if (i % p[j] == 0) { mob[i * p[j]] = 0; break; }
            mob[i * p[j]] = -mob[i];
        }
    }
}

求解流程

1. 統計每個值出現次數 cnt[x]，記錄最大值 ma。
2. 對每個 d (2..ma)，累加倍數計算 num[d] = Σ_{k} cnt[k*d]。
3. 答案 = C(n,2) + Σ_{d=2}^{ma} μ(d) * C(num[d], 2)。

關鍵代碼

ll cal() {
    ll ans = (ll)n * (n - 1) / 2;
    for (int i = 2; i <= ma; ++i) {
        num[i] = 0;
        for (int j = i; j <= ma; j += i) num[i] += cnt[j];
    }
    for (int i = 2; i <= ma; ++i)
        ans += (ll)mob[i] * num[i] * (num[i] - 1) / 2;
    return ans;
}

複雜度分析

預處理 O(MAX log log MAX)，每測試用例 O(ma log ma)（調和級數求和）。MAX=10^5 時極快，適合多測試用例。