LightOJ 1356 Prime Independence：二分圖最大獨立集

題目

集合中無兩數使一個是另一個的「質數倍」（即 a = b * prime）。求最大質數獨立子集大小。n ≤ 40000, 數值 ≤ 500000。

建模為二分圖

每個數分解質因數，質因數個數奇偶性不同的數之間才可能有「質數倍」關係（因乘一個質數改變奇偶性）。按質因數個數奇偶分為左右兩部。邊連接 (u,v) 若 u = v * prime。最大獨立集 = 總點數 - 最大匹配數（Kőnig 定理）。

算法

1. 線性篩預處理 500000 以內質數及最小質因子。
2. 計算每個數的質因數個數奇偶性。
3. 構建圖：對每個數 x，枚舉質數 p，若 x*p 在集合中加邊。
4. Hopcroft-Karp 算法求最大匹配，O(E√V) 通過大數據。
5. 答案 = n - 匹配數。

代碼框架 (C++)

// 關鍵部分：線性篩、奇偶分部、Hopcroft-Karp
// 完整代碼見原文，包含 BFS 分層、DFS 增廣、邊構建優化
// 時間複雜度 O(N log N + E√V)，空間 O(N + E)

優化點

• 只從奇部向偶部建邊（或反向），避免重複。
• 質數枚舉上限 500000/x。
• Hopcroft-Karp 用靜態數組實現隊列、邊表，避免 vector 開銷。