「算法竞技场 EP04」不会莫比乌斯也能过 Hard，手工容斥的正确打开方式！

欢迎来到「算法竞技场」EP04！我是你们的主播——老白。

（弹幕：老白你终于来了！EP03 的莫比乌斯反演把我 CPU 干烧了，我缓了三天才敢回来） （弹幕： μ 函数至今还在我梦里转圈，我现在看到希腊字母就PTSD） （弹幕：听说今天还是 GCD 主题？老白你是想把我们送走吗？）

先别急着跑！我知道上期 EP03 把大家虐得不轻——莫比乌斯反演、倍数容斥、状态图遍历……那一套组合拳下来，很多观众的脑细胞阵亡率高达 90%。但今天，我要给你们带来一个好消息，和一个坏消息。

坏消息：今天还是 GCD 主题，而且难度是 Hard。 好消息：今天的主角不是莫比乌斯函数！而是它背后那个更阳间、更接地气、更容易理解的——容斥原理！

（弹幕：？容斥原理还阳间？老白你对"阳间"的定义是不是有什么误解） （弹幕：只要不是 μ，什么都好说）

哎，别急着划走！容斥说白了就是你小学就学过的’先算总数，再扣掉重复的’——一个简单加减法的活儿，换个马甲你们就不认识了？上期五号选手用莫比乌斯反演把容斥自动化了，μ 函数的正负号就像一把精密筛网，自动把倍数层层剥掉。今天，我们来手动实现这个"剥洋葱"的过程。等你一层层亲手剥完，回头再看上期的 μ——你会恍然大悟：原来那玩意儿就是个自动剥蒜器！

（弹幕：好家伙，容斥原理被你说成小学算术） （弹幕：自动剥蒜器哈哈哈哈，莫比乌斯的棺材板都压不住了） （弹幕：所以今天是来学怎么剥洋葱的？我已经把纸巾备好了）

任务简报

悬赏令：给你一个整数数组 nums，把nums里的所有数对 (nums[i], nums[j]) (0 <= i < j < n) 的最大公约数算出来，丢进一个叫 gcdPairs 的数组里，然后升序排列。接着给你一堆查询 queries，每个查询问你：排好序的 gcdPairs 里，下标为 queries[i] 的那个数是多少？（下标从 0 开始，放心，不会越界）

数据规模警告：n <= 10^5，nums[i] <= 5 * 10^4，queries.length <= 10^5。

（弹幕：10^5 个数，数对有 5*10^9 个？这不得暴力枚举到宇宙毁灭？） （弹幕：别说排序了，光存这些 GCD 就需要 20GB 内存） （弹幕：老白，这题是不是又要用什么"不计算所有数对，直接定位第 k 小"的花活？） （弹幕：兄弟们，值域才 5e4，比 n 还小两倍，绝对是故意留的后门！）

说对了！如果我们真按任务定义去暴力——枚举所有数对、算 GCD、排序、再查第 k 个——那光枚举这一步就要 O(n²)，n=1e5 的时候就是一百亿次运算，物理上就锁定了死局。但！值域 5e4 是什么概念？这意味着你面对的是 50 亿个数对，但它们吐出来的gcd数值，翻来覆去就这五万个数！

所以，今天的核心只有一个：我不生产GCD，我只是GCD的搬运工——用数学方法直接统计**“每种 gcd 值出现了多少次”，然后用前缀和+二分**快速定位第 k 小。

有请出今天的主角：分步容斥流、同步容斥流、以及友情返场的老朋友—莫比乌斯反演流。直播正式开始！

（弹幕：妙啊！这不就是计数排序的思想吗，值域小就直接统计频次） （弹幕：我赌五毛，接下来就是“倍数统计 + 容斥剥洋葱”） （弹幕：返场是什么鬼？？不是说今天不用 μ 吗？？）

一号·分步容斥流：

一号选手缓步上台：“大家好，我的打法就六个字：拆步骤，慢慢剥。整个容斥过程我拆成了五招——导播，麻烦给个特写——”

第一招：点名签到——每个数出现了几次？

m = max(nums)
cnt = [0] * (m + 1)
for num in nums:
    cnt[num] += 1   

（弹幕：好像开学第一天老师点名……） （弹幕：这招我会，继续继续）

第二招：拉帮结派——每个数能管多少个小弟（倍数）？ 光知道每个数自己来了几次不够，还得知道每个数能‘罩着’多少个数。如果一个数是 i 的倍数，那它就能被 i 整除。

for i in range(1, m + 1):
    for j in range(i * 2, m + 1, i):
        cnt[i] += cnt[j]  # cnt[i]：nums 中有多少个数能被i整除，也就是i的所有倍数出现的总次数。

（弹幕：cnt[i] 瞬间从“i 自己”变成了“i 帮派的总人数”，简洁！） （弹幕：出现了，经典埃筛的变体——倍数倒灌） （弹幕：接下来是不是要组合数了？C(cnt[i], 2) 已经在嘴边了）

第三招：组队开黑——从人数算出多少个数对 刚才的 cnt[i] 表示能被 i 整除的数有 c 个。这 c 个数里任选 2 个组队，一共 c*(c-1)/2 个数对。这些数对的 GCD 至少是 i（因为它们都能被 i 整除），但也可能混着 2i, 3i, ...。比如 i=1 最经典，它会包括所有的数对全，因为任何两个数的 gcd 至少是 1。

for i in range(1, m + 1):
	cnt[i] = cnt[i] * (cnt[i] - 1) // 2  # cnt[i]：gcd 等于 i 的倍数 的数对有多少个。

（弹幕：C(c,2) 一出手，就知道有没有） （弹幕：原来是先求“至少是 i 的倍数”，洋葱最外层已就位）

第四招：洋葱去皮——从大到小剥掉多余的倍数层 关键来了！我们需要的是 gcd 恰好等于 i 的数对个数，可现在 cnt[i] 里还夹着 gcd 是 2i、3i 的贡献。怎么办？好办！剥洋葱打法：从大到小一层层剥！ 比如 gcd_cnt[1] 要减去 gcd_cnt[2],gcd_cnt[3],…（因为它们也贡献给了gcd_cnt[1]）

for i in range(m, 0, -1):
    for j in range(i * 2, m + 1, i):
        cnt[i] -= cnt[j]  

（弹幕：来了来了，手动剥洋葱！莫比乌斯反演的手工版！） （弹幕：所以叫"容斥"，因为我们在排除那些 GCD 是 i 的倍数但不等于 i 的情况） （弹幕：从大到小枚举，确保减的时候 gcd_cnt[j] 已经是最终值了，绝妙！）

第五招：前缀和 + 二分——快速回答查询 现在 cnt[i] 存的是 gcd 恰好等于 i 的数对数量。要快速回答第 k 小——累加 cnt ，让s[i]表示"gcd <= i 的数对有多少个"，对每个查询 q，bisect_right迅速定位到第一个使前缀和超过 q的位置，正好对应 gcd 值！

# 前缀和：从频次表变成累积排名表
s = list(accumulate(cnt))
# 每个查询直接查排名，返回对应的 gcd 值
return [bisect_right(s, q) for q in queries]

（弹幕：这不就是给 gcd 编了个排名表吗，查第几名直接翻表） （弹幕：accumulate + bisect_right，Python 标准库二连击，比 μ 函数阳间一百倍） （弹幕：五招连环，从点名到查答案，行云流水）

老白总结：来，导播把回放切出来。一号选手这五招连起来，本质上是给 gcd 的分布画了一张完整的统计画像——先统计和组队：每个数字的倍数有多少个，用C(n,2)算出能组成多少对；再手剥洋葱：从大到小容斥剥离，一层层把多余的倍数层剥掉；最后查字典：前缀和编页码，二分一秒定位。

不需要枚举任何数对，也不需要具体计算 gcd，所有的操作都在值域数组上原地完成。时间复杂度 O(m log m + Q log m)，空间 O(m)。AC 走起！

（弹幕：懂了，不枚举数对，直接统计 GCD 分布） （弹幕：这五招，比上期 μ 门好懂一百倍） （弹幕：已加入算法工具箱，下次遇到值域小的题直接套）

二号·同步容斥流：

“一号老哥，五招太墨迹了！“二号选手跳了上来，“看我两个循环，一把梭哈——”

mx = max(nums)
cnt_x = [0] * (mx + 1)

# 第一招：还是点名，老规矩
for x in nums:
    cnt_x[x] += 1

# 第二招：从大到小，边统边剥，一个循环干两份活
cnt_gcd = [0] * (mx + 1)
for i in range(mx, 0, -1):
    c = 0
    for j in range(i, mx + 1, i):
        c += cnt_x[j]				# 活一：统计 i 的倍数有多少个
        cnt_gcd[i] -= cnt_gcd[j]  	# 活二：顺手把 2i,3i 的贡献提前剥掉
    cnt_gcd[i] += c * (c - 1) // 2  # 补上“至少是 i”的数对数

# 第三招：前缀和 + 二分，老配方
s = list(accumulate(cnt_gcd))  
return [bisect_right(s, q) for q in queries]

（弹幕：卧槽？这就完了？） （弹幕：等等，内层循环里 cnt_gcd[i] -= cnt_gcd[j] 的时候，cnt_gcd[i] 不还是 0 吗？减空气？） （弹幕：楼上问得好，这就是从大到小的妙处——你看着是 0，等循环跑完就不是了）

老白解说：二号选手把一号的手剥洋葱法升级成了“流水线削皮”！他的这手**“同步容斥”**，确实是把一号的五招压缩成了三招，精髓全在那个 for i in range(mx, 0, -1) 的内层循环里。

咱们拿 i=6 来走一遍。内层循环依次拜访 6、12、18、24……

• 碰到 6：把 6 的出现次数加进 c。
• 碰到 12：把 12 的出现次数加进 c，同时把 cnt_gcd[12]（已经算好的“gcd 恰好等于 12”的数对数）从 cnt_gcd[6] 里扣掉。！！有人会问：cnt_gcd[6] 现在不是 0 吗？没错，就是 0！但没关系——虽然我现在扣成负数了，但等会儿会加回来，先欠着，而且，因为 12 比 6 大，已经在之前的循环里被处理干净了，剥掉的cnt_gcd[12] 是精确值。
• 碰到 18、24……同理，一边加c，一边减倍数贡献值。

等内层循环跑完，c 装满了“能被 6 整除的总人数”，cnt_gcd[6] 变成了一个负数——它已经把 gcd 恰好等于 12、18、24……的数对贡献全减干净了。这时候补一句 cnt_gcd[6] += c * (c - 1) // 2，把“gcd 至少是 6”的数对总数加回去。一负一正，恰好抵消，剩下的就是** gcd 精确等于 6 的数对数**。算完了。

（弹幕：懂了，先赊账，再还款，这波是算法信用卡！） （弹幕：一号：我先把所有 c 算好，再倒着剥。二号：我边跑边剥，跑完也剥完了） （弹幕：所以“同步容斥”就是边统边剥，一个循环当两个用） （弹幕：优雅，太优雅了，利用从大到小遍历一次就把所有活干了）

老白敲黑板：一号和二号本质上是同一套逻辑，区别只在执行顺序。一号是先把所有“倍数人数”算好存起来，再从容斥循环里取用——干净，但多跑了一轮循环。二号是直接在容斥循环里现算 c，多算一次就多扣一次——代码更短，时间还是 O(m log m)，但常数更小，跑得更快。

（弹幕：从大到小，边统边剥，一步到位！） （弹幕：懂了，面试官问"如何优化”，就甩出这套同步容斥秒杀） （弹幕：我选二号，代码短就是正义！） （弹幕：三号是返场的μ 门吗？我已经闻到莫比乌斯反演的味道了） （弹幕：来了来了！μ 门返场！！）

三号·莫比乌斯反演流·友情返场

一道裹着深蓝色斗篷的人影从后台阴影中踱步而出，他走向黑板，像画符一样写下——「μ」。

m = max(nums)
cnt = [0] * (m + 1)

# 1：点名
for num in nums:
    cnt[num] += 1
    
# 2：后倍数倒灌  
for i in range(1, m + 1):
    for j in range(i * 2, m + 1, i):
        cnt[i] += cnt[j]

# 3：组合数，“gcd 是 i 的倍数”的数对数量
for i in range(1, m + 1):
    cnt[i] = cnt[i] * (cnt[i] - 1) // 2

# 4：μ 函数一键容斥
mu = [0] * (m + 1)
mu[1] = 1
for i in range(1, m + 1):
    for j in range(i * 2, m + 1, i):
        mu[j] -= mu[i]

g = [0] * (m + 1)
for i in range(1, m + 1):
    for k in range(1, m // i + 1):
        g[i] += mu[k] * cnt[i * k]

# 5：前缀和 + 二分，老规矩
s = list(accumulate(g))
return [bisect_right(s, q) for q in queries]

（弹幕：这代码比一号还长，说好的“全自动更省力”呢？？） （弹幕：μ 门返场，但今天一号二号已经把容斥讲透了，我看你怎么圆）

斗篷人的声音就像自带混响：“一号的倒着减，二号的边统边剥，和我这个 μ 加权求和——本质上都是容斥。区别只在操作手法——他们是手动控制加减，我是用 μ 函数自动控制加减。”

他指向中间那段 μ 的代码：“mu[1]=1, mu[2]=-1, mu[3]=-1, mu[6]=1…… 这些正负号，正好对应着容斥里‘先加后减，减完再加’的节奏。一号二号是手工剥洋葱，我这个是给洋葱配了一张自动剥皮指令表。”

（弹幕：所以莫比乌斯函数就是一张“容斥系数表”？提前算好正负号？？） （弹幕：懂了！μ(k) 就是容斥的“快捷键”，不用自己倒着枚举了） （弹幕：一号：我手动判断该减谁。二号：我边跑边判断。三号：我掏出小抄直接抄答案？）

“什么小抄？！这是数学界的奥义！ μ 就是一个智能过滤器，自动帮你完成容斥逻辑。你不需要手动判断该减谁，μ 函数会告诉你系数是多少——”，斗篷人顿了一下，“——就像是开着外挂打游戏。”

老白赶紧圆场：三号的意思其实特简单——你们把那段 μ 的代码当成黑盒子用就行。输入 cnt（倍数统计表），输出 g（恰好等于表）。盒子里面 μ 函数怎么跳的正负号不用管，只需要知道：它等价于一号的倒着减，也等价于二号的边统边剥。 三种写法，一套数学内核。

不过说句公道话，今天值域 5 万，二号那个‘边统边剥’已经又快又短又好看了。莫比乌斯反演更适合多维、复杂的倍数关系。咱们今天的三号出场，纯属友情返场，也好让大家下次见到莫比乌斯反演不用怕，它不是什么玄学，就是把容斥的加减号提前帮你标好了。你今天手剥过洋葱，以后再用 μ，心里就有底了。

（弹幕：懂了，莫比乌斯是"自动挡”，手工容斥是"手动挡"） （弹幕：今天这题用 μ 确实是大炮打蚊子，二号完全够用） （弹幕：我今天终于理解了容斥的本质：先算总数，再减去不想要的）

伤害统计 & 赛后锐评

老白擦汗：好了，今天的 EP04 虽然没有上期那么炸裂，但这套"倍数容斥 + 前缀和二分"的组合拳，绝对是能陪你闯荡周赛、活过面试的贴身装备。导播，切数据面板！！

（弹幕：一号胜在清晰，二号胜在精悍，三号胜在……仪式感） （弹幕：我选一号，我怕面试时被面试官问住）

老白的出装推荐——请选择你的英雄：

• 面试求生：选一号。逻辑清晰，面试官一看就懂你在用容斥原理，是"数学思维 + 工程能力"的双重证明。
• 周赛竞速：选二号。“从大到小，边统边剥”六个字概括核心逻辑。代码短，跑得快，秒出答案。
• 数论炫技：如果你想吓唬人，三号 μ 门直接安排。比如，在面试结尾提一句"这题其实也可以用莫比乌斯反演，但没必要"，逼格拉满。

（弹幕：所以今天的精髓在于"不枚举数对，只统计 GCD 分布"，学到了！） （弹幕：值域小的题就往值域上想，这句话值一个 offer） （弹幕：μ 门传承 + 洋葱心法，两期联动太爽了）

尾声：

好了，今天的「算法竞技场 EP04」到此全部打板收工！觉得这期让你对容斥原理有了新的理解，把**「洋葱剥明白了」**打在公屏上！Bug 清零，Offer 拿到手软，所有 gcd 查询都精确命中！我是老白，在 EP05 的副本门口蹲你，咱们下期见！

本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。