HDU 5072 Coprime：同色三角形計數 + 容斥原理 + 莫比烏斯反演優化

問題建模

N 個點，紅/黑兩色。任意三點形成三角形，同色三角形指三頂點同色。總三角形數 C(N,3)。求同色三角形數 = 總數 - 非同色數。

非同色三角形計數公式

設點 i 連接紅點 R_i 個、黑點 B_i 個。非同色三角形每條「異色邊」被計算兩次（兩端點各一次），故：

非同色數 = Σ(R_i × B_i) / 2

核心難點：高效計算 R_i, B_i

「異色」定義為 gcd(x,y) > 1（非互質）。需對每個點 i，統計與它互質/不互質的點數。N≤10^5，暴力 O(N^2) 不可行。

莫比烏斯反演優化

• 預處理每數的質因子分解（線性篩）
• 利用容斥：某點值 v 的倍數個數 = Σ μ(d) * cnt[d] (d|v)
• 維護 cnt[d]：值為 d 的倍數的點數
• 動態更新：遍歷點時實時更新 cnt，查詢當前已處理點中的互質數

關鍵代碼邏輯

// 預處理質因子
for (int i=2; i<=MAX; i++) if (!vis[i]) {
    primes.push_back(i);
    for (int j=i; j<=MAX; j+=i) { vis[j]=1; fac[j].push_back(i); }
}

// 遍歷點計算答案
for (int i=1; i<=n; i++) {
    int v = a[i];
    // 利用容斥計算與 v 不互質的已處理點數
    int not_coprime = 0;
    for (int mask=1; mask < (1<>k&1) { d*=fac[v][k]; bits++; }
        not_coprime += (bits&1 ? 1 : -1) * cnt[d];
    }
    int coprime = processed - not_coprime;
    // 更新答案...
    for (int d : divisors[v]) cnt[d]++; // 更新倍數計數
    processed++;
}

複雜度分析

• 質因子分解預處理：O(MAX log log MAX)
• 每點容斥枚舉子集：質因子數 ≤ 6 (2×3×5×7×11×13=30030>10^5)，子集 ≤ 63
• 總計：O(N × 2^ω) ≈ 6×10^6，極快

避坑指南

• 同色三角形 = 總數 - 非同色數，非同色數公式除以 2 別忘
• 莫比烏斯函數 μ 通過質因子個數奇偶性隱含實現
• 長整型防止溢出 (N≤10^5, C(N,3) ~ 10^15)