※ 引述《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了 对ㄚ