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 的常數是否足夠?是否需要進一步優化?
- 如果查詢是動態的(元素會被加入或刪除),如何維護答案?