第一次看到 P2398 GCD SUM 这个题我的第一反应是这不就是两个 for 套一个 gcd 吗题目要求的东西非常直白给定一个正整数 n计算所有 1≤i≤n、1≤j≤n 的数对 (i,j) 的 gcd 之和。但刷题这么多年我早就养成了一个习惯先别急着写循环先看一眼数据范围再决定策略。这道题的 n 上限是 100000如果直接枚举 i 和 j数对总量是 10^10就算 gcd 写得再快也扛不住。所以这道题真正的考点不是“你会不会求 gcd”而是“你能不能把求和式子化简成一个可以预处理、可以分块计算的形式”。这篇文章我就把完整的推导过程、代码实现和几个容易踩的坑一起写出来适合刚接触数论题、想搞懂欧拉函数和数论分块怎么配合使用的朋友。1. 先看清题目到底在求哪个东西1.1 暴力三重循环为什么一上来就该被否掉题面浓缩起来就一行ans ∑_{i1}^{n} ∑_{j1}^{n} gcd(i, j)很多新手看到这个式子的直觉就是枚举 i、j然后调 __gcd 累加。代码确实短短到十行以内就能写完long long ans 0; for (int i 1; i n; i) for (int j 1; j n; j) ans gcd(i, j);但这种写法在 n100000 时完全跑不动。n² 已经是 10^10gcd 内部还要做若干次取模运算总计算量轻松突破 10^11。评测环境里这属于必超时的方案代码再短也没有意义。竞赛里遇到“求和式子里带着 gcd、lcm 这类数论函数”的题目我的经验是立刻换思路不去枚举数对而是枚举函数值。gcd(i,j) 的取值只可能是 1 到 n 之间的整数那我们就按 gcd 的取值 d 来分桶数清楚每个桶里有多少个数对最后统一加权求和。1.2 枚举 d把求和对象从“数对”换成“gcd 值”设 cnt[d] 表示满足 gcd(i,j)d 的有序数对 (i,j) 数量。因为每一对数对都会恰好落入某一个 d 对应的桶里所以答案可以写成ans ∑_{d1}^{n} d * cnt[d]这个变形把问题拆成了两块外面这层 d 的求和很好处理后面甚至能用等差数列合并真正麻烦的是 cnt[d] 怎么求。如果只是求“gcd(i,j) 是 d 的倍数”的数对个数那太简单了i 和 j 都得是 d 的倍数数量就是 ⌊n/d⌋²。但“恰好等于 d”要严格得多它要求 i/d 和 j/d 不能再有公共因子。这一步处理好了整道题就通了。2. 核心推导用 φ 函数统计互质数对2.1 从“恰好等于 d”到“a、b 互质”我们先把“gcd(i,j)d”翻译成更可操作的条件。如果最大公约数正好是 d那么 i 和 j 都是 d 的倍数可以写成i d * a j d * b并且 gcd(a,b) 必须等于 1。反过来也成立只要 a、b 互质那么 da 和 db 的最大公约数就恰好是 d不会多也不会少。因为 i、j 都不超过 n所以 a、b 都在 1 到 ⌊n/d⌋ 之间。令 m⌊n/d⌋那么 cnt[d] 就变成了一个纯粹的计数问题在 a,b ∈ [1,m] 中满足 gcd(a,b)1 的有序数对有多少个“有序”这个词要划重点因为题目里的 (i,j) 和 (j,i) 是不同的数对后面计数公式里那个“减 1”就是因为这个。2.2 互质有序对计数公式2×φ前缀和−1先回忆欧拉函数 φ(x) 的定义1 到 x 中与 x 互质的正整数个数。它天然适合回答“如果固定 b x那么有多少个 a≤b 满足 gcd(a,b)1”答案就是 φ(x)。如果我们把 b 从 1 枚举到 m把 φ(b) 累加起来得到的是所有满足 a≤b 且互质的有序对数量。这个数量我记为S(m) ∑_{b1}^{m} φ(b)但这只统计了“a 在左边、b 在右边”的一半情况。对于任意 ab 且互质的数对题目里还应该有 (b,a) 这一组它们互为对称。除了 (1,1) 这种对角线上的特例其他每个互质对都能对称出一组新的有序对。所以最终的有序互质对总数是cnt[d] 2 * S(m) - 1减掉的 1 就是 (1,1) 被重复计算的那一次。把 φ(1)1 也纳入 S(m)公式就变得非常干净2 倍前缀和再整体减 1。2.3 手算验证公式不会漏也不会重这个公式第一次见的人容易心里打鼓我建议自己手算一遍。拿 m3 举例a、b 都在 {1,2,3} 里互质的有序对一共是下面 7 组(1,1)、(1,2)、(2,1)、(1,3)、(3,1)、(2,3)、(3,2)而 φ(1)1φ(2)1φ(3)2所以 2S(3)-1 2(112)-1 7完全一致。再看 m4φ(4)2S(4)62*6-111。把所有 16 组有序对列出来去掉 (2,2)、(3,3)、(4,4) 以及 (2,4)、(4,2)剩下的确实是 11 组。算到这里答案表达式已经浮出水面了ans ∑_{d1}^{n} d * ( 2*S(⌊n/d⌋) - 1 )现在的问题就变成了怎么快速得到 S(m)也就是 φ 的前缀和。2.4 用样例数据把公式跑一遍拿 n4 手算验证。φ(1)1φ(2)1φ(3)2φ(4)2所以 S(1)1S(2)2S(3)4S(4)6。d⌊n/d⌋2*S(⌊n/d⌋)-1d * 该项141111223631134114累加得到 1163424和题目样例输出一致。公式从第一道坎就站住了后面可以放心往下写代码。3. 预处理欧拉函数线性筛而不是逐个分解质因数3.1 积性函数与三个关键递推公式里需要 S(m)也就是 φ 的前缀和。n 最大才 100000第一反应可能是对每个数暴力分解质因数再套 φ(n)n*∏(1-1/p) 的公式。那样做总复杂度大概是 O(n√n)在这个数据范围也能跑但不够优雅而且一旦题目把 n 加到 10^7这个方案立刻崩盘。正确做法是线性筛。欧拉函数是积性函数只要 gcd(a,b)1就有 φ(a*b)φ(a)*φ(b)。线性筛求 φ 依赖下面三条递推若 p 是素数那么 φ(p)p-1若当前数 i 与素数 p 互质那么 φ(i*p)φ(i)φ(p)φ(i)(p-1)若 p 整除 i说明 p 已经出现在 i 的质因数分解中此时 φ(i*p)φ(i)*p。第 3 条初看有点反直觉p 已经存在了为什么只是乘 p 而不是乘 p-1因为 p 作为一个质因子早就在 i 里了i*p 和 i 的质因数集合完全相同互质数的“占比”没有变只是数本身变大了 p 倍所以 φ 直接乘 p。3.2 线性筛求 φ 的完整写法一个标准的筛法实现如下const int MAXN 100000 5; int phi[MAXN]; long long prefPhi[MAXN]; bool notPrime[MAXN]; vectorint primes; void init(int n) { phi[1] 1; for (int i 2; i n; i) { if (!notPrime[i]) { primes.push_back(i); phi[i] i - 1; } for (int p : primes) { long long v 1LL * i * p; if (v n) break; notPrime[v] true; if (i % p 0) { phi[v] phi[i] * p; break; } else { phi[v] phi[i] * (p - 1); } } } for (int i 1; i n; i) { prefPhi[i] prefPhi[i - 1] phi[i]; } }这里有几个细节值得专门说一下。phi[1] 必须手动设置为 1。这不是可选项而是公式成立的前提。前文所有涉及 S(m) 的地方如果 φ(1) 是 0那么 2*S(m)-1 从一开始就全错了。当 i%p0 时一定要 break。欧拉筛之所以是线性的靠的就是“每个合数只被它的最小质因子筛掉一次”。如果不 break同一个合数会被多个质因子重复标记性能会退化到接近埃氏筛甚至更差。v 用 long long 和 n 比较这个习惯能防止 i*p 在 int 里溢出。本题 n 只有 1e5 还看不出问题但如果哪天把这份代码搬到 n1e9 的题目里这个细节能直接救命。3.3 为什么不直接对每个数求 φ有人会觉得这道题 n 才 1e5我暴力分解每个数求 φ 也很快啊何必费劲写线性筛这话有一定道理在只求 AC 的前提下暴力确实能过。但刷题不能只盯着单题欧拉函数、莫比乌斯函数这类积性函数的线性筛预处理是数论题里复用率极高的工具。我见过太多人平时不练筛法一到需要预处理 φ 的题就临时写暴力最后在小数据上 AC换个大数据就被卡死。把线性筛写成肌肉记忆遇到 n 很大的同类题目能直接无缝迁移这个投资很值。另外线性筛求 φ 的代码量真的很小和暴力分解相比并没有复杂多少。与其留一个“数据一变大就要重构”的隐患不如一次写到位。4. 数论分块把最后的求和压到 O(√n)4.1 观察 ⌊n/d⌋ 的分段特性公式已经到手直接 for d1 到 n 累加复杂度 O(n)对于 1e5 的数据完全能过。但我想多说一步因为这道题的答案公式天生适合数论分块学会之后能应付更大数据范围。观察 ⌊n/d⌋ 这个值的变化。它随 d 增大而递减但不是每一步都变而是一段一段地跳。比如 n10 时d1234、56~10⌊n/d⌋105321值相同的 d 会聚成连续的区间整个 [1,n] 只被分成大约 2√n 段。理解这个结论可以换个角度当 d≤√n 时d 本身最多只有 √n 种取法当 d√n 时⌊n/d⌋ √n商最多也只有 √n 种取法。两边一夹段数自然就是 O(√n)。既然每一段里的 ⌊n/d⌋ 都相同那么 (2*S(⌊n/d⌋)-1) 在这一整段里都是常数完全可以提到求和号外面把 d 的贡献一次性算掉。4.2 分块的写法与代码细节假设当前处理到的左端点是 l令 m n/l那么满足 ⌊n/d⌋ m 的最远右端点就是 r n/m。这一段的贡献为∑_{dl}^{r} d * (2S(m)-1) (2S(m)-1) * ∑_{dl}^{r} d后面那个 d 的求和是等差数列直接用 (lr)*(r-l1)/2 计算。完整 AC 代码如下#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint phi(n 1); vectorlong long pref(n 1); vectorbool notPrime(n 1, false); vectorint primes; primes.reserve(n / 10); phi[1] 1; for (int i 2; i n; i) { if (!notPrime[i]) { primes.push_back(i); phi[i] i - 1; } for (int p : primes) { long long v 1LL * i * p; if (v n) break; notPrime[v] true; if (i % p 0) { phi[v] phi[i] * p; break; } phi[v] phi[i] * (p - 1); } } for (int i 1; i n; i) pref[i] pref[i - 1] phi[i]; long long ans 0; for (long long l 1, r; l n; l r 1) { long long m n / l; r n / m; long long sumD (l r) * (r - l 1) / 2; ans sumD * (2 * pref[(int)m] - 1); } cout ans \n; return 0; }分块最容易写错的就是右端点 rn/m。我第一次学这个技巧的时候总想着 rn/(m1) 之类更“精确”的式子结果把自己绕晕了。记住一个固定套路m 由左端点算出来右端点一定等于 n/m别犹豫。至于为什么 l、r、m、sumD 都用 long long是因为虽然 n 只有 1e5但 (lr)*(r-l1) 这个中间量在更大范围内会超过 int。写题时宁可全开 long long 也不用去赌“这次数据没那么大”。4.3 三种算法的复杂度对比方案复杂度n1e5 时的情况枚举 i、j 再求 gcdO(n² log n)完全不可行线性筛 φ d 从 1 到 n 直接循环O(n)可以通过线性筛 φ 数论分块O(n √n)可以通过且常数极小如果只求 ACO(n) 的朴素求和已经足够。但我还是推荐把分块写上去原因很简单答案表达式天然就是“常数段求和”的形状分块写起来不比直接循环复杂遇到 n 变成大数的同类型题还能继续用。5. 验证、易错点和另一种推导路线5.1 边界数据与一致性检查代码写完别急着交先手测几个小数据n1只有 (1,1) 一组答案就是 1。分块时 [1,1] 这一段的 m1pref[1]12*1-11sumD1答案 1正确。n2四对 gcd 分别是 1、1、1、2总和 5。公式d1 时 1*(2S(2)-1)3d2 时 2(2*S(1)-1)2总和 5正确。n4前面手算过24与样例一致。更稳妥的做法是写一个暴力枚举函数和正解对拍几百组随机小数据。这种方法能一次性覆盖大量边界情况比肉眼检查放心得多。5.2 三个容易踩的坑第一个坑答案和中间量必须用 long long。n100000 时最终答案在 10^10 级别int 直接溢出。这没什么技巧凡是可能变大的量一律 long long。第二个坑φ(1) 忘记初始化为 1。筛法循环通常从 2 开始phi 数组默认全是 0如果少了 phi[1]1 这一步pref[1] 就会变成 0后面每一段的 (2*S-1) 都会系统性偏小。这已经不是“差一点点”的问题而是公式整体失效。第三个坑分块右端点写错。典型症状是小数据答案没问题n 变大后答案偏偏少一段。右端点如果算小了会漏掉区间尾部的数对算大了又会把下一段的值混进来导致后续 l、r 全部错位。所以务必记住 rn/m 这个固定写法。5.3 莫比乌斯反演视角殊途同归如果熟悉莫比乌斯反演这道题还有另一条推导路线。设 F(k) 表示 gcd(i,j) 是 k 的倍数的数对个数显然 F(k)⌊n/k⌋²。再设 f(k) 表示 gcd(i,j) 恰好等于 k 的数对个数由莫比乌斯反演f(k) ∑_{t1}^{⌊n/k⌋} μ(t) * F(k*t)代入答案式并换元 Tk*t可以得到ans ∑_{T1}^{n} ⌊n/T⌋² * ∑_{k|T} k*μ(T/k)内层 ∑_{k|T} k*μ(T/k) 正是 φ(T) 的经典表达。于是最终得到另一个同样简洁的公式ans ∑_{T1}^{n} φ(T) * ⌊n/T⌋²这个形式和前面推出来的 2*S(⌊n/d⌋)-1 看起来完全不同但数值上完全一致。两条路线最后都落在欧拉函数上这件事本身就说明这道题的数学本质就是对互质数对计数φ 是绕不开的主角。我个人写这道题更偏爱第一种推导因为每一步都有明确的计数含义代码里只需要 φ 前缀和不用额外处理 μ。但如果你想检验自己的反演功底第二种推导是很好的练习题也能作为题解里的“彩蛋”写给读者看。这道题隔一段时间重新做一次我都会提醒自己同一个原则看到双重求和先想换序看到 gcd 先想按值分桶。把“枚举数对”转化成“枚举函数值”这一步想通了后面线性筛、数论分块都只是常规动作。