HardRating 2533
3312. Sorted GCD Pair Queries
arrayhash-tablemathbinary-searchcombinatoricscountingnumber-theoryprefix-sum
解題說明
Sorted GCD Pair Queries
題目描述：給定一個整數陣列 nums 和查詢陣列 queries。對於所有 (i, j) 配對（i < j），計算 gcd(nums[i], nums[j]) 並將所有 GCD 值排序。對每個查詢 queries[k]，回傳排序後的第 queries[k] 個 GCD 值（0-indexed）。
解題思路：直接枚舉所有配對的 GCD 不可行（O(n²)），需要用數論技巧。對於每個可能的 GCD 值 g（1 到 max(nums)），計算有多少配對的 GCD 恰好為 g。令 cnt[g] 為 nums 中 g 的倍數的個數，則 GCD 為 g 的倍數的配對數為 C(cnt[g], 2)。再用莫比烏斯容斥：exact[g] = C(cnt[g], 2) - exact[2g] - exact[3g] - ...（從大到小計算）。最後對 exact 做前綴和，對每個查詢用二分搜尋找到對應的 GCD 值。
C++ 解法
複雜度分析
時間複雜度：O(M log M + Q log M) — M 為 max(nums)。計算 cnt 陣列為 O(M log M)（調和級數），莫比烏斯容斥為 O(M log M)，每個查詢二分搜尋 O(log M)。
空間複雜度：O(M + Q) — 頻率、計數、前綴和陣列各 O(M)，答案陣列 O(Q)。
虛擬碼
1. Count frequency of each value in nums 2. For g = 1 to max: cnt[g] = sum of freq[m] for m = g, 2g, 3g, ... 3. For g = max down to 1: exact[g] = C(cnt[g], 2) - sum of exact[kg] for k >= 2 4. Build prefix sum array of exact[] 5. For each query q: binary search for smallest g where prefix[g] > q 6. Return answers
其他解法
暴力枚舉 O(n² log V)：枚舉所有配對計算 GCD 後排序。在 n 大時完全不可行。
篩法 + 離線排序查詢 O(M log M + Q log Q)：將查詢離線排序，依序掃描 GCD 值分配答案。可避免二分搜尋但需要額外的排序步驟。
延伸思考
- 如果要求的是 LCM 而非 GCD，數論技巧如何調整？
- 如果 nums 中的元素可達 10⁶，M log M 的常數是否足夠？是否需要進一步優化？
- 如果查詢是動態的（元素會被加入或刪除），如何維護答案？