HDU 5072 Coprime：互質三元組計數與容斥原理

問題描述

n 個互不相同的整數 a_i (≤1e5)，選 3 個數使其兩兩互質 或 兩兩不互質。求三元組個數。n ≤ 1e5, T ≤ 5。

補集轉化：單色三角形模型

• 構建完全圖，邊染色：互質為紅，不互質為藍。
• 目標：單色三角形（全紅或全藍）數量。
• 總三角形 C(n,3) - 非單色三角形。

非單色三角形計數

每個非單色三角形恰有 2 顆頂點連紅邊、1 顆連藍邊（或相反）。枚舉中間頂點 i，設與 i 互質的點數為 c_i，不互質為 n-1-c_i。以 i 為「特殊頂點」的非單色三角形數 = c_i * (n-1-c_i)。總和除以 2（每個三角形被計算兩次）。

核心難點：快速求每個數的互質個數

利用容斥原理。預處理 1..1e5 每個數作為因子出現的次數 cnt[d]。對每個 a_i，分解質因子，容斥計算與其不互質的數，得互質數 = n-1 - 不互質數。

算法流程

1. 篩法預計算質數表（至 500 即可，因 500²>1e5）。
2. 統計 cnt[d]：每個 a_i 的所有因數 d 計數++。
3. 對每個 a_i，提取質因子，容斥求不互質數，得 c_i。
4. 累加 c_i * (n-1-c_i)，最後 ans = C(n,3) - sum/2。

複雜度

• 預處理因數：O(n * sqrt(maxA)) 或倍數枚舉 O(maxA log maxA)。
• 單次查詢：質因子數 ≤ 6，容斥 2^6=64 子集，極快。
• 總體：O(maxA log maxA + n * 2^ω) 約 1e6 量級，輕鬆過限。

總結

本題將組合計數轉化為圖論單色三角形，再利用容斥高效計算互質關係。關鍵技巧：補集思維、因數頻率預處理、質因子分解與容斥。是數論與組合結合的優秀練習題。