解題說明
GCD Sort of an Array
題目描述：給定一個整數陣列 nums，可以任意次交換兩個元素 nums[i] 和 nums[j]，前提是 gcd(nums[i], nums[j]) > 1。判斷是否能透過這些操作將陣列排序為非遞減順序。
解題思路：若兩個數共享質因子，它們可以互換。透過傳遞性，共享相同質因子的所有數屬於同一個連通分量，分量內的數可以任意排列。使用 Union-Find 將每個數與其所有質因子合併。最後檢查：對每個位置 i，nums[i] 和排序後的 sorted[i] 是否在同一連通分量中。若是，則可排序。
C++ 解法
複雜度分析
時間複雜度：O(M log log M + n log M) — 篩法 O(M log log M)，質因數分解每個數 O(log M)，Union-Find 操作近乎 O(1)。M = max(nums)。
空間複雜度：O(M) — 篩法陣列和 Union-Find 陣列。
虛擬碼
1. Compute smallest prime factor (SPF) sieve up to max(nums) 2. Initialize Union-Find with max(nums)+1 elements 3. For each number x in nums: a. Factorize x using SPF sieve b. Union(x, each prime factor of x) 4. Sort a copy of nums 5. For each position i: a. If Find(nums[i]) != Find(sorted[i]): return false 6. Return true
其他解法
直接 GCD 圖 + BFS/DFS：對每對元素計算 GCD，GCD > 1 則加邊，用 BFS 找連通分量。時間 O(n^2 log M)，n 大時過慢。
質因數分組：用雜湊表按質因子分組，同組的數可互換。需要合併共享質因子的組。等價於 Union-Find 解法但用不同視角實作。
延伸思考
- 若交換條件改為 lcm(nums[i], nums[j]) <= threshold，問題如何變化？
- 若要求最少交換次數使陣列排序，如何計算？
- 若陣列可以有重複元素，解法是否需要修改？