双周赛一结束我先把第 178 场 Q2 这道 101005 重新敲了一遍。题目名很直白数对的最大公约数之和。给你一个数组让你求所有下标 ij 的数对的 gcd 之和。如果你照着题面暴力枚举大概率会收获一排超时但如果能把“枚举数对”改成“枚举公约数”整个题目就变成一道经典计数题。这篇文章我会从题意翻译开始讲清楚为什么暴力不可行、f[d] 和 g[d] 的容斥关系怎么推再给出 C 和 Python 的完整实现最后聊聊这类题怎么迁移到其他计数场景。适合正在刷双周赛、准备面试手撕数论题或者想补一补“约数倍数计数”套路的朋友。1. 先把题目读透这题到底在问什么1.1 从题意到数学表达题目叫“数对的最大公约数之和”翻译成数学语言其实就一句话给定长度为 n 的数组 nums计算S sum_{0 i j n} gcd(nums[i], nums[j])。也就是说把所有“不同下标”的数对全部拎出来求每一对的最大公约数再全部加起来。下标不同就算不同数对哪怕两个位置的数值相等也要按两个数对分别计算。为了后面推公式方便我造一个例子nums [6, 10, 15]。三对数分别是gcd(6, 10) 2gcd(6, 15) 3gcd(10, 15) 5总和是 2 3 5 10。这个例子很小手算都能出答案后面我会反复用它来验证推导和代码。这里有一个容易忽略的点题目只要求“数对”不要求“连续子数组”或者“排列”。所以没有任何顺序上的限制纯粹是在 n 个位置里任选两个。这个“任选两个”的语义很重要它决定了我们后面要用组合数而不是别的计数方式。1.2 先看数据范围再定策略竞赛里做数论题第一件事不是想公式而是先看 n 和数值范围。以这类题最常见的约束为例n 可以到 10^5 甚至 2×10^5数组里的每个值也可以到 2×10^5 级别。如果题目只给 O(n^2) 的做法那基本是送分题但这题放在双周赛 Q2显然不会让你两重循环直接过。“数对”的数量是 n(n-1)/2。当 n 10^5 时这个数字大约是 5×10^9就算 gcd 本身只需要几十个周期5 亿次 gcd 调用也是不可接受的更不用说 50 亿次。哪怕你把 gcd 换成查表、换成位运算优化瓶颈依然在数对数量本身。所以核心思路必须从“遍历数对”跳出来改成“遍历可能的公约数”。这个方向在数论题里特别常见凡是要求“所有数对的某个函数之和”如果函数只依赖于两个数的约数关系那就可以考虑枚举约数而不是枚举数对。gcd 恰恰是这种函数因为 gcd(a, b) 一定是 a 和 b 的公共约数我们可以把问题转换成“统计有多少数对同时能被某个 d 整除”再想办法从这些“至少”的统计量里还原出“恰好”的数量。2. 暴力思路为什么不行以及第一个优化方向2.1 枚举数对的复杂度先承认一个事实暴力解法非常简单代码三行就能写完long long ans 0; for (int i 0; i n; i) for (int j i 1; j n; j) ans gcd(nums[i], nums[j]);这个逻辑完全没有问题问题只出在规模上。n 10^5 时内层循环要跑大约 5×10^9 次。哪怕一次 gcd 只要 50 纳秒整体也要几百秒妥妥的超时。n 如果到 2×10^5数对数量会到 2×10^10 级别彻底没戏。还有一个隐性成本现代 CPU 对随机访问大数组并不友好两重循环里 nums[i] 和 nums[j] 的访存模式会带来大量 cache miss。所以暴力解法不只是时间复杂度高实际运行还会更慢。竞赛里遇到这种“翻译题面就能做”的题目一定要条件反射地怀疑一下数据范围。2.2 从“枚举数对”到“枚举公约数”既然不能枚举数对那我们就枚举可能的 gcd 值。假设数组最大值为 M那么任何数对的 gcd 都不可能超过 M所以 d 的范围是 1 到 M。先定义一个计数数组 cnt[x]表示数值 x 在数组中出现了多少次。这个数组的构建只需要 O(n) 时间。接着对于每个 d我们想知道有多少个元素能被 d 整除。把这个数量记为 s_ds_d sum_{x 是 d 的倍数} cnt[x]。一旦知道了 s_d我们就能知道“至少能被 d 整除”的数对数量在 s_d 个元素里任选两个组合数是 C(s_d, 2)。我把它记作 f[d]f[d] s_d * (s_d - 1) / 2。回到 [6, 10, 15] 这个例子。当 d 1 时三个数都能被 1 整除s_1 3f[1] 3这表示一共有 3 对数对它们的 gcd 至少是 1。当 d 2 时能被 2 整除的是 6 和 10s_2 2f[2] 1。同样d 3 时 f[3] 1d 5 时 f[5] 1。如果直接把所有 f[d] 加起来会得到 3 1 1 1 6但正确答案是 10明显不对。原因很简单一对 gcd 为 2 的数对不仅被 f[2] 统计到也会被 f[1] 统计到因为 1 也能整除这两个数。也就是说f[d] 统计的是“gcd 至少为 d”的数对而不是“gcd 恰好为 d”的数对。因此我们需要一个从“至少”到“恰好”的转换工具。这个工具就是容斥递推。3. 正解容斥递推统计 gcd 恰好等于 d 的数对数量3.1 定义 cnt[x] 和 f[d]先把完整的流程写出来。第一步统计每个数值的出现次数。设 mx 为数组最大值申请一个长度为 mx 1 的 cnt 数组遍历 nums执行 cnt[nums[i]]。第二步对于每个 d计算 s_d 和 f[d]。s_d 是能被 d 整除的元素个数f[d] 是 s_d 个元素里任选两个的组合数。这里要特别注意f[d] 会把“gcd 恰好等于 d、2d、3d……”的所有数对全部混在一起。如果用 g[d] 表示“gcd 恰好等于 d”的数对数量那么对任意正整数 d都有f[d] g[d] g[2d] g[3d] g[4d] ...这个等式非常关键。它的意思是两个数如果能同时被 d 整除那它们的 gcd 一定是 d 的某个倍数。反过来说如果一对数的 gcd 恰好是 kd那么它们一定同时被 d 整除所以会被记入 f[d]。所有 kd 的情况叠加起来就是完整的 f[d]。3.2 从 f[d] 反推 g[d]有了上面的等式我们就可以从大到小反推 g[d]。因为 g[d] 只依赖于所有 g[2d]、g[3d]、g[4d]……这些下标都比 d 大的值。所以只要从 mx 开始往下循环当计算 g[d] 时所有 g[2d]、g[3d] 等等都已经算好了。计算公式是g[d] f[d] - (g[2d] g[3d] g[4d] ...)整理成代码就是g[d] f[d] for (m 2 * d; m mx; m d) g[d] - g[m]算完 g[d] 之后它对答案的贡献是 d * g[d]因为一共有 g[d] 个数对它们的 gcd 都恰好是 d。最后把所有贡献加起来就是题目要求的答案。回到 [6, 10, 15] 这个例子。mx 15我们从大到小算。所有 g[7] 到 g[15] 都是 0。g[6] f[6] - g[12] - ... 0因为能被 6 整除的元素只有 6 一个f[6] 0。逐步算到 d 5f[5] 1所以 g[5] 1。d 3f[3] 1g[3] 1。d 2f[2] 1g[2] 1。d 1f[1] 3但要减去 g[2] g[3] g[5] ... 1 1 1 3所以 g[1] 0。最后答案2 × g[2] 3 × g[3] 5 × g[5] 2 3 5 10。这和手算结果完全一致。3.3 复杂度分析这个做法的时间复杂度是 O(M log M)其中 M 是数组最大值。为什么不是 O(M^2)因为计算每个 d 的倍数时内层循环不是从 1 到 M而是从 d 开始每次加 d。总循环次数大约是M/1 M/2 M/3 ... M/M M × (1 1/2 1/3 ... 1/M)。这个括号里的调和级数大约是 ln M 欧拉常数所以总复杂度就是 O(M log M)。当 M 2×10^5 时总操作次数也就是两三百万级别跑起来非常快。空间上需要三个长度为 mx 1 的数组cnt、f、g。每个都是 long long空间大概是 3 × 2×10^5 × 8 字节差不多 5MB完全没问题。4. 代码实现与细节4.1 C 实现下面是我在比赛结束后整理的 C 版本函数签名按照常见的 LeetCode 风格来写class Solution { public: long long sumGcdOfPairs(vectorint nums) { int mx 0; for (int x : nums) mx max(mx, x); vectorint cnt(mx 1, 0); for (int x : nums) cnt[x]; vectorlong long f(mx 1, 0), g(mx 1, 0); // 计算每个 d 的倍数元素个数并得到 f[d] for (int d 1; d mx; d) { long long s 0; for (int m d; m mx; m d) { s cnt[m]; } f[d] s * (s - 1) / 2; } long long ans 0; // 从大到小反推 g[d] for (int d mx; d 1; d--) { g[d] f[d]; for (int m d d; m mx; m d) { g[d] - g[m]; } ans d * g[d]; } return ans; } };这里有几个细节值得说。第一cnt 数组的类型用 int 就够了因为每个数值出现次数最多是 nn 到 2×10^5 不会爆 int。但 s 和 f 必须用 long long因为 s 最大也是 ns × (s - 1) / 2 在 n 2×10^5 时大约是 2×10^10已经超出 int 范围。第二g[d] 最终一定是一个非负整数它表示恰好有多少数对的 gcd 等于 d。如果你在调试时发现某个 g[d] 变成了负数那多半是 f 数组算错了或者循环顺序写反了。第三mx 是数组最大值不是数组长度。有人习惯用 n 来做数组边界但 nums[i] 的最大值可能远大于 n也可能远小于 n。用 mx 才能保证所有倍数都能被枚举到。4.2 Python 实现Python 版本思路完全一样只是要注意 Python 在大量循环时比 C 慢所以要尽量少做不必要的操作。from typing import List class Solution: def sumGcdOfPairs(self, nums: List[int]) - int: mx max(nums) cnt [0] * (mx 1) for x in nums: cnt[x] 1 f [0] * (mx 1) g [0] * (mx 1) for d in range(1, mx 1): s 0 for m in range(d, mx 1, d): s cnt[m] f[d] s * (s - 1) // 2 ans 0 for d in range(mx, 0, -1): g[d] f[d] for m in range(d d, mx 1, d): g[d] - g[m] ans d * g[d] return ans这段代码在数据范围 2×10^5 时在 LeetCode 环境下通常能在 1 到 2 秒内跑完。如果你担心 Python 速度可以把 cnt、f、g 从列表改成 array 模块的数组或者把内层循环里的mx 1提前存成局部变量都能略微提升一点性能。4.3 几个容易踩的坑第一个坑是答案的数据范围。即使 f 和 g 都用了 long long最终 ans 也可能是更大数量级的数字。比如说有 10^5 个数全是 10^6那么每对 gcd 都是 10^6数对数量约 5×10^9答案约 5×10^15这个量级必须用 64 位整数。C 里一定用long longPython 则天然支持大整数不用担心。第二个坑是重复数值。如果数组里有多个相同的数比如 [4, 4, 4]cnt[4] 3那么 f[1] 和 f[2] 和 f[4] 都会用到这个 3。我们需要的是“不同下标”的数对而组合数 C(3, 2) 恰好表示从三个位置里选两个能正确数出 3 对数对不会多也不会少。这个性质很重要千万别在 cnt 统计后去重否则答案就错了。第三个坑是循环边界。计算 g[d] 时倍数要从 2d 开始不能从 d 开始否则会把 g[d] 自己减掉结果全变 0。我开始写的时候还犯过这个低级错误debug 了很久才发现。5. 常见问题与排查技巧实录5.1 为什么 f[d] 要开 long long很多初学者会问s_d 不是最多 n 吗int 够啊问题出在组合数上。C(n, 2) n × (n - 1) / 2当 n 10^5 时大约是 4.99995×10^9超过 int 的 21 亿上限。一旦 n 到 2×10^5这个值接近 2×10^10int 完全装不下。所以只要你的代码里出现了s * (s - 1) / 2s 哪怕只是一个 int在相乘时也会溢出。正确做法是先把 s 放到 long long 里再计算。Python 没有这个问题但 C 必须注意。5.2 小数据对拍验证这类计数题最容易出现“样例过了但提交全错”的情况。我强烈建议写一个暴力函数专门用来和小数据对拍。long long brute(vectorint nums) { int n nums.size(); long long res 0; for (int i 0; i n; i) { for (int j i 1; j n; j) { res __gcd(nums[i], nums[j]); } } return res; }然后随机生成 n 在 10 以内、数值在 1 到 20 之间的数组对比暴力结果和优化结果。只要随机测几千组都一致代码基本就稳了。这个方法对任何数论计数题都通用比肉眼检查可靠得多。5.3 常见错误速查表现象可能原因解决办法结果总是偏大直接把 f[d] 累加了没有做容斥用 g[d] f[d] - sum(g[2d], g[3d], ...)结果总是偏小循环从 d 开始把自己减掉了倍数从 2d 开始出现负数g[d] 减多了或 f[d] 溢出检查 long long 和递推顺序运行超时两层循环每次都从头扫确保内层是m d而不是m边界越界数组开到 n 而不是 mx用 max_element 获取最大值6. 这题背后还能怎么用从双周赛到实际场景6.1 另一个更简洁的公式欧拉函数恒等式如果你对数论比较熟会发现这道题还有一个更漂亮的等价做法。对任意正整数 x都有一个恒等式x sum_{d | x} phi(d)这里的 phi 是欧拉函数。也就是说一个数的值等于它的所有约数对应的欧拉函数之和。那么 gcd(a, b) 就可以写成gcd(a, b) sum_{d | gcd(a, b)} phi(d)把这个等式代入“所有数对的 gcd 之和”交换求和顺序就得到S sum_{d1}^{mx} phi(d) × C(s_d, 2)注意这里的 s_d 和前面一样还是“能被 d 整除的元素个数”。这个公式不需要维护 f 数组和 g 数组只需要先筛出 phi再枚举 d 的倍数累加答案。复杂度同样是 O(M log M)但代码更简洁也不容易写错。两种方法本质上是相通的容斥递推里的 g[d] 等价于按约数关系做莫比乌斯反演而欧拉函数恒等式则是直接构造了一个“权重函数”。如果你在比赛里时间紧张用欧拉函数版本会更快。6.2 这类“计数不重不漏”思路的迁移这道题最有价值的不是它本身而是“f[d] 到 g[d]”的容斥模型。以后遇到下面这些题目都可以套用求所有数对中 gcd 恰好等于 1 的数量。求所有数对中 lcm 的和或数量。求所有数对的公因子数量之和。求数组中互质数对的数量。核心套路都是三步先统计 cnt再枚举 d 算 s_d最后用容斥、莫比乌斯反演或欧拉函数把“至少”转成“恰好”。一旦你熟练掌握这套模型很多数论计数题都能在几分钟内拆解成模板题。6.3 从“数对”到“多元组”的扩展如果把“两两数对”改成“任意 k 个数的 gcd 之和”思路也一样只是组合数 C(s_d, 2) 要改成 C(s_d, k)。比如求所有三元组的 gcd 之和就用 C(s_d, 3)。甚至可以把 C 换成其他多项式只要它能表示选 k 个元素的计数方式即可。这个扩展在数学建模和数据分析里也有影子当你要计算一组样本中多个对象的最大公约数分布时本质上就是在做这种约数计数。我个人的体会是这道题在双周赛里属于“看起来简单、推起来有点绕”的类型。真正把它吃透之后你会发现所有复杂度都花在调和级数枚举上代码本身并不长。最后再分享一个小技巧如果比赛里来不及证明容斥关系就先写欧拉函数版本phi 筛法只要背下来5 分钟内能写完正确率也更高。