企业官网建设流程全解析

双周赛一结束，我先把第 178 场 Q2 这道 101005 重新敲了一遍。题目名很直白：数对的最大公约数之和。给你一个数组，让你求所有下标 i<j 的数对的 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) = 2
• gcd(6, 15) = 3
• gcd(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_d：

s_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 = 3，f[1] = 3，这表示一共有 3 对数对，它们的 gcd 至少是 1。当 d = 2 时，能被 2 整除的是 6 和 10，s_2 = 2，f[2] = 1。同样，d = 3 时 f[3] = 1，d = 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 = 5，f[5] = 1，所以 g[5] = 1。d = 3，f[3] = 1，g[3] = 1。d = 2，f[2] = 1，g[2] = 1。d = 1，f[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(vector<int>& nums) { int mx = 0; for (int x : nums) mx = max(mx, x); vector<int> cnt(mx + 1, 0); for (int x : nums) cnt[x]++; vector<long 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 就够了，因为每个数值出现次数最多是 n，n 到 2×10^5 不会爆 int。但 s 和 f 必须用 long long，因为 s 最大也是 n，s × (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 long，Python 则天然支持大整数，不用担心。

第二个坑是重复数值。如果数组里有多个相同的数，比如 [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^10，int 完全装不下。

所以只要你的代码里出现了s * (s - 1) / 2，s 哪怕只是一个 int，在相乘时也会溢出。正确做法是先把 s 放到 long long 里再计算。Python 没有这个问题，但 C++ 必须注意。

5.2 小数据对拍验证

这类计数题最容易出现“样例过了但提交全错”的情况。我强烈建议写一个暴力函数，专门用来和小数据对拍。

long long brute(vector<int>& 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 常见错误速查表

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_{d=1}^{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 分钟内能写完，正确率也更高。