HDU 5072 Coprime：互質三角形計數與容斥原理應用

HDU 5072 Coprime 解題報告：單色三角形轉化 + 容斥原理

給定 n 個數 a[i]，求三元組 (i, j, k) 的數量，使得 gcd(a[i], a[j], a[k]) == 1。等價於「總三角形數 - 至少有一對不互質的三角形數」。

核心轉化：單色三角形模型

構造完全圖，點為數組元素。若 gcd(a[i], a[j]) > 1 連紅邊，否則黑邊。題目求「非單色三角形」數（即三邊不全紅）。

對於任意非單色三角形，必存在一個頂點連接紅、黑兩色邊。設 d[i] 為點 i 的紅邊度數（即與其不互質的點數），則黑邊度數為 n-1-d[i]。該頂點貢獻的「紅黑混合角」數為 d[i] * (n-1-d[i])。每個非單色三角形恰有兩個這樣的頂點，故：

非單色三角形數 = Σ d[i]*(n-1-d[i]) / 2

答案 = C(n,3) - 非單色三角形數

關鍵難點：高效計算 d[i]

n ≤ 10^5，a[i] ≤ 10^6。直接 O(n^2) 求 gcd 不可行。利用 容斥原理 + 質因子分解：

1. 預處理：對每個 a[i] 質因子分解，得到不重複質因子集合 ele[]。
2. 對每個質因子組合（子集），統計「能被該組合整除的數的個數」cnt[mask]。
3. 查詢 d[i]：對 a[i] 的質因子集合，容斥計算「與其不互質的數的個數」。

關鍵代碼邏輯

// 質因子分解
void factorize(int x) {
    num = 0;
    for(int p=2; p*p<=x; ++p) if(x%p==0) {
        ele[num++] = p;
        while(x%p==0) x/=p;
    }
    if(x>1) ele[num++] = x;
}

// 預處理 cnt[mask]
void init() {
    memset(cnt, 0, sizeof(cnt));
    for(int i=0; i

複雜度分析

質因子分解：O(√a[i])，最多 ~7 個不同質因子（2*3*5*7*11*13*17 > 10^6）。
子集枚舉：O(2^7) = O(128)。
總時間：O(n * 128)，完全滿足限制。


易錯點

long long 防溢出（C(n,3) ≈ 1.6e15）。
容斥時 mask=0 不參與（空集無意義）。
cnt 數組大小需覆蓋最大質因子乘積（10^6 以內）。