※ 引述《sixB (6B)》之銘言：
: 問完gpt
: 他說就是要n^2欸
: 到底有沒有料ㄚ==
沒提示我也不會寫 從來不打周賽 我就爛
3312. Sorted GCD Pair Queries
思路
數字最大才5*10^4
直接反過來對所有 < 5*10^4 的整數去算他是幾個組合的GCD
用排容從上往下算
對正整數k 組數是 因數有k的組數 - 最大公因數是n*k的組數
因數有k的組數就直接先算完所有數字出現次數
再去找k, 2k, 3k... 總和算C取2
最後維護一個長度為max(num)的陣列
用來表達累積組數
拿查詢的index去裡面二分搜就是答案了
瞎機巴敲一敲
def gcdValues(self, nums, queries):
n = len(nums)
m = max(nums) + 1
counted = [0] * m
gcd_count = [0] * m
accum = [n * (n - 1) // 2] * m
l = 0
result = [None] * len(queries)
for i in range (n):
counted[nums[i]] += 1
for i in range (m - 1, 1, -1):
k = 0
sub = 0
for j in range(i, m, i):
k += counted[j]
sub += gcd_count[j]
gcd_count[i] = k * (k - 1) // 2 - sub
l += gcd_count[i]
accum[i-1] -= l
accum[0] = 0
for i in range(len(queries)):
result[i] = bisect_right(accum, queries[i])
return result
哩扣的分析跟我說時間複雜度O(N+M)
我也懶得想對不對 反正AC了 對ㄚ