HardRating 2221
1627. Graph Connectivity With Threshold
arraymathunion-findnumber-theory
解題說明
Graph Connectivity With Threshold
題目描述： 有 n 個城市（編號 1 到 n）。兩個城市 a 和 b 之間存在道路，當且僅當存在一個大於 threshold 的整數 z，使得 z 同時整除 a 和 b（即 z 是 a 和 b 的公因數）。給定若干查詢 [a, b]，判斷 a 和 b 是否連通。
解題思路： 使用並查集（Union-Find）。對每個大於 threshold 的整數 z，將 z 的所有倍數合併到同一個集合。具體地，遍歷 z 從 threshold+1 到 n，將 z, 2z, 3z, ... 依次合併。這樣，有公因數 > threshold 的城市自然會在同一個集合中。每次查詢只需判斷 find(a) == find(b)。
C++ 解法
複雜度分析
時間複雜度：O(n log n × alpha(n) + Q × alpha(n)) — 建圖的外層迴圈為調和級數 O(n log n)，每次 union 操作 O(alpha(n))，Q 次查詢各 O(alpha(n))
空間複雜度：O(n) — 並查集的 parent 和 rank 陣列
虛擬碼
1. Initialize Union-Find with n+1 nodes
2. For z from threshold+1 to n:
a. For each multiple mult = 2z, 3z, ... up to n:
- Unite(z, mult)
3. For each query [a, b]:
a. Answer true if find(a) == find(b), else false
4. Return results其他解法
方法二：GCD 暴力檢查 對每對城市計算 gcd(a, b)，如果 gcd > threshold 則連邊，然後用 BFS/DFS 或並查集判斷連通性。時間複雜度 O(n^2 log n)，對於大 n 不可行。
方法三：篩法（Sieve）+ BFS 類似質因數篩法，先找出每個數的因數，然後建立鄰接表再 BFS。時間複雜度與本解法類似但實現較複雜。
延伸思考
- 如果 threshold 是 0，問題會簡化成什麼？所有城市都會連通嗎？
- 這個問題中的 union 操作和埃拉托斯特尼篩法（Sieve of Eratosthenes）有什麼結構上的相似之處？
- 如果查詢是動態的（threshold 會改變），如何有效地更新連通性？