蓝桥杯既约分数题解：从暴力枚举到欧拉函数线性筛优化

1. 从一道填空题看"既约分数"的暴力枚举边界

蓝桥杯2020年初赛有一道填空题，题目编号1509，问的是在1到2020的范围内，有多少对互质的整数(i, j)，也就是分子分母最大公约数为1的分数有多少个。这道题看起来简单到令人发指——不就是两层循环加一个gcd吗？但真正动过手的人都知道，这里面藏着几个非常典型的坑，尤其是当你把范围从2020放大到10^5甚至10^6的时候，暴力解法的性能瓶颈会瞬间暴露出来。

我第一次做这道题的时候，脑子里第一反应就是双重循环枚举所有(i, j)组合，然后对每一对调用gcd判断是否等于1。写出来大概十行代码，跑2020的范围几乎是秒出结果。但后来我在想，如果题目把范围改成10^5呢？10^6呢？甚至10^7呢？暴力法的复杂度是O(n² log n)，n=2020的时候大约是4×10^6次操作，完全没问题；但n=10^5的时候就是10^10次操作，直接爆炸。所以这道题虽然是一道填空题，但它背后其实牵扯到一个非常经典的数论问题——欧拉函数求和，也就是我们常说的法里数列（Farey sequence）的项数问题。

这篇文章我会从这道题出发，把暴力枚举的写法、欧拉函数优化的思路、线性筛的实现细节、以及实际比赛中可能遇到的各种边界情况全部拆开讲清楚。不管你是刚接触蓝桥杯的新手，还是已经刷了几百道题想回头巩固数论基础的老手，应该都能从中找到一些有用的东西。尤其是那些"看起来会做但一写就错"的细节，我会重点标出来。

2. 暴力枚举能过，但你必须知道它为什么能过

2.1 最直观的双重循环写法

先看最朴素的解法。题目要求统计1 ≤ i, j ≤ 2020且gcd(i, j) = 1的有序对数量。注意这里i和j是对称的，也就是说(1, 2)和(2, 1)算两组不同的解，因为分数1/2和2/1是不同的分数。这一点很多人第一遍会搞混，以为只算一半然后乘2就行——乘2确实可以，但前提是你把对角线上的情况处理对。

import math count = 0 for i in range(1, 2021): for j in range(1, 2021): if math.gcd(i, j) == 1: count += 1 print(count)

这段代码跑出来答案是2481215。我当时第一次跑的时候还担心会不会超时，结果Python也就跑了不到两秒，C++更是毫秒级出结果。原因很简单：2020² ≈ 4.08×10^6，每次gcd运算是O(log n)级别，总的操作量大概在几千万次这个量级，现代CPU完全扛得住。

但这里有个细节值得注意：Python的math.gcd是C实现的，速度比自己手写欧几里得算法快很多。如果你在比赛里用Python写了一个纯Python的gcd函数，那跑2020的范围可能就要五六秒了。所以即使用暴力法，也要尽量调用标准库。

2.2 对称性优化：少算一半

既然(i, j)和(j, i)是对称的，那我们可以只枚举i < j的情况，然后结果乘2，再加上对角线上的情况。对角线就是i = j，这时候gcd(i, i) = i，只有i = 1的时候gcd才等于1。所以对角线只贡献1个解，就是(1, 1)。

import math count = 0 for i in range(1, 2021): for j in range(i + 1, 2021): if math.gcd(i, j) == 1: count += 1 count = count * 2 + 1 # 乘2加上对角线(1,1) print(count)

这样内层循环的次数大约减少了一半，实际运行时间也会相应缩短。不过对于2020这个范围来说，优化效果感知不明显，真正有价值的是当n变大的时候，这种对称性优化能帮你省掉一半的时间。

2.3 暴力法的真正边界在哪里

我实测过几个不同的n值，用C++写的暴力法（调用std::gcd），大致的时间如下：

可以看到，C++在n=10000的时候还能勉强撑住，但到了50000就基本不行了。Python的瓶颈更早出现，n=5000的时候就已经很难受了。所以如果你的题目范围超过10^4，就不要再想着暴力枚举了，必须上数论方法。

注意：蓝桥杯的填空题通常只要求提交最终答案，不要求提交代码，所以即使你用暴力法跑几分钟，只要能在比赛时间内出结果就行。但如果是编程大题，时限通常是1到2秒，暴力法就完全不可行了。

3. 欧拉函数是怎么把O(n²)压到O(n)的

3.1 从"计数互质对"到"求和欧拉函数"

暴力法的本质是枚举每一对(i, j)然后判断。但如果我们换一个角度：对于每个固定的j，有多少个i满足gcd(i, j) = 1且i ≤ n？这个数量其实就是欧拉函数φ(j)的定义——小于等于j且与j互质的正整数个数。但注意，欧拉函数φ(j)统计的是1到j之间与j互质的数的个数，而我们这里i的范围是1到n（n可能大于j）。

等等，这里有个容易搞混的地方。题目中i和j的范围都是1到2020，是对称的。如果我们固定j，i从1到2020，那么满足gcd(i, j) = 1的i的个数并不是φ(j)，因为φ(j)只统计到j为止。但是！由于gcd(i, j) = gcd(i mod j, j)，实际上i在1到2020范围内与j互质的个数，等于在1到j范围内与j互质的个数乘以一个系数——不对，这个说法也不准确。

让我重新理一下。对于固定的j，i从1到n，满足gcd(i, j) = 1的i的个数，当n是j的倍数时，恰好等于(n/j) × φ(j)。但2020并不是每个j的倍数，所以不能直接这样算。

正确的思路是这样的：我们要求的是Σ_{i=1}^{n} Σ_{j=1}^{n} [gcd(i, j) = 1]。利用对称性，我们可以把它写成2 × Σ_{i=1}^{n} Σ_{j=i+1}^{n} [gcd(i, j) = 1] + 1（加1是对角线的(1,1)）。

但更常用的方法是直接利用欧拉函数的性质。对于每个j，在1到j范围内与j互质的数有φ(j)个。而在1到n范围内，与j互质的数的个数可以这样算：把1到n分成若干个长度为j的区间，每个完整区间内有φ(j)个与j互质的数，最后不完整的区间单独处理。但这样算起来还是比较麻烦。

实际上，对于这道题n=2020的情况，我们有一个更简洁的观察：由于i和j的范围相同，我们可以直接计算Σ_{j=1}^{n} φ(j)再乘以2再减1。为什么？因为Σ_{j=1}^{n} φ(j)统计的是所有满足1 ≤ i ≤ j ≤ n且gcd(i, j) = 1的有序对(i, j)的数量。由于对称性，i > j的情况和i < j的情况数量相同，所以总的互质对数量 = 2 × Σ_{j=1}^{n} φ(j) - 1（减1是因为对角线(1,1)被重复计算了一次）。

这个公式是成立的，但前提是i和j的范围相同。如果范围不同，就不能这样简单处理了。

3.2 欧拉函数的计算：从试除法到线性筛

单个欧拉函数的计算可以用试除法，复杂度O(√n)。但如果要对1到n的所有数都求欧拉函数，逐个试除的总复杂度是O(n√n)，对于n=2020来说完全没问题，但对于n=10^6来说就太慢了。

更高效的方法是使用线性筛（欧拉筛）来同时求出所有数的欧拉函数值。线性筛的核心思想是每个合数只被它的最小质因子筛掉一次，所以总复杂度是O(n)。在筛的过程中，我们可以顺便递推求出每个数的欧拉函数值。

递推公式是这样的：设p是质数，对于数x：

• 如果x是质数，φ(x) = x - 1。
• 如果x = y × p且p是y的最小质因子（即p | y），那么φ(x) = φ(y) × p。
• 如果x = y × p且p不整除y，那么φ(x) = φ(y) × (p - 1)。

这个递推关系的证明需要用到欧拉函数的积性性质，这里不展开，但记住结论就行。

def euler_sieve(n): phi = [0] * (n + 1) primes = [] is_composite = [False] * (n + 1) phi[1] = 1 for i in range(2, n + 1): if not is_composite[i]: primes.append(i) phi[i] = i - 1 for p in primes: if i * p > n: break is_composite[i * p] = True if i % p == 0: phi[i * p] = phi[i] * p break else: phi[i * p] = phi[i] * (p - 1) return phi

这段代码是线性筛求欧拉函数的标准写法。有几个细节需要注意：

第一，phi[1]要初始化为1，因为φ(1) = 1（1与1互质）。第二，内层循环中当i % p == 0时，说明p是i的最小质因子，此时phi[i * p] = phi[i] * p，然后直接break，保证每个合数只被筛一次。第三，当i % p != 0时，p不是i的因子，所以phi[i * p] = phi[i] * (p - 1)。

3.3 最终答案的组装

有了欧拉函数表之后，答案就是2 × Σ_{j=1}^{2020} φ(j) - 1。

n = 2020 phi = euler_sieve(n) total = sum(phi[1:n+1]) answer = 2 * total - 1 print(answer)

跑出来结果还是2481215，和暴力法一致。但这个方法的时间复杂度是O(n)，n=2020的时候几乎是瞬间出结果，即使n=10^7也能在一秒内跑完（C++），Python的话大概两三秒。

提示：如果你在比赛中只需要提交答案，用暴力法其实更省事，因为不容易写错。但如果你想提升自己的数论能力，或者题目范围很大，那线性筛求欧拉函数是必须掌握的技能。

4. 那些年我在欧拉函数上踩过的坑

4.1 边界条件：φ(1)到底等于几

欧拉函数的定义是：小于等于n且与n互质的正整数的个数。对于n=1，小于等于1且与1互质的正整数只有1本身，所以φ(1) = 1。这个看起来很简单，但很多人在写线性筛的时候会忘记初始化phi[1]，导致phi[1] = 0，最后答案差1。

我在第一次写线性筛的时候就把phi[1]漏掉了，结果跑出来答案比正确答案少1。当时排查了半天，以为是筛法写错了，后来才发现是phi[1]没有初始化。这个坑非常隐蔽，因为对于大多数n > 1的情况，phi[n]都是正数，只有phi[1]是特殊的。

4.2 整数溢出：答案可能超出int范围

对于n=2020，答案是2481215，这个数在int范围内（int最大约21亿）。但如果n更大呢？Σφ(j)的增长速度大约是3n²/π²，所以答案大约是6n²/π²。当n=10^5的时候，答案大约是6×10^10/9.87 ≈ 6×10^9，已经超过了int的范围（约2.1×10^9）。当n=10^6的时候，答案大约是6×10^12/9.87 ≈ 6×10^11，需要long long才能存下。

所以在写代码的时候，计数器变量一定要用long long（C++）或者Python的int（Python自动处理大整数）。我见过不少人在比赛中因为用了int导致结果溢出，最后答案变成一个负数或者奇怪的数。

4.3 线性筛的break条件写反

线性筛的核心是"每个合数只被它的最小质因子筛掉一次"。实现这个目标的关键是内层循环中的break条件：当i % p == 0时，说明p是i的最小质因子，此时筛掉i * p之后就应该break，因为后面的质数p' > p不可能是i * p'的最小质因子（p才是）。

但很多人在写的时候会把break条件写反，写成i % p != 0时break，或者干脆不写break。不写break的话，复杂度就退化成O(n log log n)甚至更高，虽然对于n=2020来说感知不明显，但对于n=10^7来说就会明显变慢。

# 错误写法：break条件写反 for p in primes: if i * p > n: break is_composite[i * p] = True if i % p != 0: # 这里写反了 phi[i * p] = phi[i] * (p - 1) break else: phi[i * p] = phi[i] * p

这种错误写法会导致某些合数被重复筛掉，而且phi值的递推也会出错。正确的写法一定是i % p == 0时break。

4.4 对称性公式的适用条件

前面提到的公式"答案 = 2 × Σφ(j) - 1"有一个前提：i和j的范围相同。如果题目改成i从1到n，j从1到m且n ≠ m，这个公式就不适用了。这时候需要更复杂的处理方法，比如用莫比乌斯反演或者分段求和。

蓝桥杯这道题恰好是i和j范围相同，所以可以用这个简化公式。但如果你在别的题目中遇到范围不同的情况，千万不要直接套这个公式。

5. 从2020到10^7：性能实测与优化选择

5.1 不同n值下的方法选择

我整理了一个对照表，方便你在不同场景下选择合适的方法：

对于蓝桥杯这道题，n=2020，暴力法完全够用。但如果你是在准备更高级别的比赛，或者想系统学习数论，那线性筛求欧拉函数是必须掌握的。

5.2 线性筛的内存优化

当n=10^7的时候，phi数组需要10^7个int，大约40MB（C++）或80MB（Python，因为Python的int对象更大）。如果内存限制比较紧，可以考虑用一些技巧来压缩空间。

一个常用的技巧是：不需要同时保存is_composite和phi两个数组，可以用phi数组本身来标记合数。具体做法是初始化phi[i] = i，然后在筛的过程中修改。但这样会稍微增加代码的复杂度，对于大多数比赛来说没必要。

另一个技巧是使用bitset来存储is_composite，这样可以把布尔数组的空间压缩到原来的1/8。但Python中没有原生的bitset，需要用bytearray或者int来模拟。

5.3 Python的性能瓶颈与应对

Python在做大规模数值计算的时候确实比C++慢很多。对于n=10^6，Python的线性筛大概需要2到3秒，而C++只需要0.1秒左右。如果比赛允许使用PyPy，速度会快很多，大概能提升3到5倍。

如果只能用CPython，那可以考虑用numpy来加速。但numpy不太适合写筛法这种有复杂控制流的代码，所以提升有限。另一个思路是用C扩展或者ctypes调用C代码，但这在比赛中通常不允许。

所以如果你用Python打比赛，遇到n很大的数论题，要么想办法优化算法（比如用杜教筛），要么就换C++。这也是为什么很多蓝桥杯选手最终都转C++的原因——不是Python不好，而是某些场景下Python确实力不从心。

6. 这道题还能怎么变：几个值得思考的扩展方向

6.1 如果范围不是从1开始

原题的范围是1到2020。如果改成从L到R（L > 1），那答案就不能直接用Σφ(j)来算了。因为欧拉函数统计的是从1开始的互质数个数，而从L开始的话，需要减去1到L-1中与j互质的数的个数。

这时候可以用容斥原理，或者用莫比乌斯反演来处理。具体来说，要求Σ_{i=L}^{R} Σ_{j=L}^{R} [gcd(i, j) = 1]，可以转化为Σ_{d=1}^{R} μ(d) × (⌊R/d⌋ - ⌊(L-1)/d⌋)²。这个公式用到了莫比乌斯函数μ(d)，是数论中非常强大的工具。

6.2 如果要求的是无序对

原题中(i, j)和(j, i)算不同的解，因为分数1/2和2/1是不同的。但如果题目改成统计无序对（即{i, j}和{j, i}算同一个），那答案就变成了Σφ(j)（不再乘2减1）。这个变化看起来很小，但如果你在比赛中看错了题目要求，就会直接丢分。

6.3 如果要求的是最简分数之和

原题只要求统计个数。如果改成求所有最简分数的和，那就变成了另一个问题。对于每个j，所有以j为分母的最简分数的和是(1/j) × Σ_{i与j互质, i≤j} i。这个求和有一个已知的公式：当j > 1时，Σ_{i与j互质, i≤j} i = j × φ(j) / 2。所以每个j贡献的分数和是φ(j) / 2。总的分数和就是Σφ(j) / 2。这个结论在数论中很经典，但推导过程需要一些技巧。

6.4 如果n大到10^9

当n大到10^9的时候，线性筛的O(n)空间和时间都不可接受了。这时候需要用杜教筛来求Σφ(j)的前缀和。杜教筛的复杂度是O(n^(2/3))，对于n=10^9来说大约需要10^6次操作，完全可行。

杜教筛的核心思想是利用狄利克雷卷积的性质：φ * 1 = id（其中1是常数函数，id是恒等函数）。通过这个卷积关系，可以推导出Σφ(j)的递推公式，然后用记忆化搜索来加速计算。这部分内容比较进阶，蓝桥杯初赛通常不会考到，但如果你在准备ACM或者更高级别的比赛，值得花时间研究一下。

7. 我在实际编码中的一些习惯和体会

写这类数论题的时候，我养成了几个习惯，分享出来供参考。

第一个习惯是先用暴力法验证小范围。比如对于n=10的情况，我会先手算或者用暴力法跑出答案，然后再用优化方法跑一遍，对比结果是否一致。这样可以快速发现公式推导或者代码实现中的错误。很多人在写线性筛的时候，直接跑n=2020，结果错了也不知道错在哪里，因为答案太大了没法手算验证。

第二个习惯是把中间结果打印出来。比如在写线性筛的时候，我会先打印出前20个phi值，看看是不是和已知的欧拉函数序列一致（φ(1)=1, φ(2)=1, φ(3)=2, φ(4)=2, φ(5)=4, φ(6)=2, φ(7)=6, φ(8)=4, φ(9)=6, φ(10)=4...）。如果前几个值就不对，那说明筛法写错了，不用继续往下跑。

第三个习惯是注意数据类型的范围。前面提到过，答案可能超出int范围，所以计数器一定要用long long。另外，在计算phi[i] * p的时候，如果n很大，phi[i] * p也可能溢出int，所以phi数组本身也要用long long。但这样会浪费一倍的内存，所以更好的做法是判断一下n的范围，如果n ≤ 10^5，用int就够了；如果n更大，再用long long。

第四个习惯是在比赛前准备好模板。线性筛求欧拉函数是一个非常标准的模板，我通常会提前写好并测试好，比赛的时候直接复制粘贴。这样既能节省时间，又能避免手写出错。但前提是你必须完全理解模板的每一行代码，否则一旦题目有变化，你就不知道怎么改了。

提示：蓝桥杯的填空题只要求提交答案，不要求提交代码。所以如果你对线性筛不够熟练，完全可以用暴力法跑出答案然后直接填。但如果是编程大题，就必须写出高效的代码。所以平时练习的时候，两种方法都要掌握。

8. 关于这道题的一些零散思考

这道题表面上是考欧拉函数，但实际上它考的是你对"互质"这个概念的理解深度。很多人看到"既约分数"三个字就懵了，不知道什么是既约分数。其实既约分数就是最简分数，也就是分子分母互质的分数。理解了这一点，题目就变成了"统计1到2020范围内互质的整数对数量"。

另外，这道题也提醒我们，蓝桥杯的填空题并不总是"简单题"。有些填空题的思维难度甚至比编程大题还高，因为它要求你不仅会写代码，还要能推导出数学公式。如果你只会暴力枚举，遇到n很大的填空题就束手无策了。

最后说一个我在比赛中的真实经历。有一次我遇到一道类似的填空题，范围是1到10^6，我第一反应是用暴力法，但估算了一下时间发现要跑好几个小时，肯定来不及。于是我现场推导了欧拉函数的公式，用线性筛跑出了答案。虽然推导过程花了十几分钟，但最终节省了大量时间。所以平时多掌握一些数论工具，在关键时刻真的能救命。

对于这道1509题，如果你只是想快速拿到答案，暴力法完全够用。但如果你想通过这道题真正提升自己的数论水平，我建议你至少把线性筛求欧拉函数的写法练熟，并且理解背后的递推原理。这样下次遇到类似的问题，你就能从容应对了。