1. 项目概述为什么我们需要“线性筛法求欧拉函数”如果你正在刷算法题或者研究数论大概率会遇到这样一个问题给定一个正整数n需要快速求出1到n之间每个数的欧拉函数值。最直接的想法是对每个数i用公式φ(i) i * Π(1 - 1/p)p是i的质因数单独计算。这个方法的时间复杂度是O(n * sqrt(n))当n达到10^6甚至10^7这个量级时这个复杂度是完全不可接受的程序会超时到让你怀疑人生。这时候“筛法”就登场了。筛法的核心思想不是“单独计算”而是“批量生产”。我们熟知的埃拉托斯特尼筛法埃氏筛可以高效地筛选出一定范围内的所有素数。那么我们能不能在筛选素数的同时也把每个数的欧拉函数值给“筛”出来呢这就是“筛法求欧拉函数”要解决的问题。而“线性筛法”又称欧拉筛则是筛法中的效率王者它保证了每个合数只被其最小质因子筛掉一次从而将整体时间复杂度降到了严格的O(n)。因此“线性筛法求欧拉函数模板”就成了解决此类大数据量欧拉函数前缀和问题的标准答案和必备武器。它不仅仅是背一段代码更是理解数论中质因数分解、积性函数与高效算法结合的关键。2. 核心原理拆解欧拉函数的积性与线性筛的适配性要理解模板为什么那样写必须先搞清楚两个核心概念欧拉函数的积性以及线性筛是如何运作的。2.1 欧拉函数的定义与积性欧拉函数φ(n)表示的是小于等于n的正整数中与n互质的数的个数。例如φ(8) 4与8互质的数有1,3,5,7。积性函数是数论中的一个重要概念。如果一个定义在正整数上的函数f(n)满足对于任意两个互质的正整数a和b即gcd(a, b) 1都有f(a*b) f(a) * f(b)那么f(n)就是积性函数。欧拉函数正是一个积性函数。这意味着如果我们能把一个数n分解成若干个两两互质的因子之积那么φ(n)就等于这些因子的欧拉函数值的乘积。特别地对于质数p有φ(p) p - 1因为1到p-1都与p互质。对于质数的幂p^k有φ(p^k) p^k - p^(k-1) p^(k-1) * (p - 1)。这个性质是我们推导递推公式的基础。2.2 线性筛欧拉筛的运作机制线性筛之所以是线性的关键在于它用一个数组primes存储已发现的素数并确保每个合数i * primes[j]只被其最小质因子primes[j]筛掉一次。它的核心框架如下以C为例const int N 10000010; int primes[N], cnt; // primes[]存储所有素数cnt是计数 bool st[N]; // st[x]存储x是否被筛掉非素数 void get_primes(int n) { for (int i 2; i n; i) { if (!st[i]) primes[cnt] i; // i是素数加入列表 for (int j 0; primes[j] n / i; j) { st[primes[j] * i] true; // 用当前素数primes[j]筛掉合数 i*primes[j] if (i % primes[j] 0) break; // 关键保证只被最小质因子筛一次 } } }理解if (i % primes[j] 0) break;这一行是理解整个算法的钥匙当i % primes[j] 0时说明primes[j]是i的一个质因子且由于我们从小到大遍历素数primes[j]一定是i的最小质因子。此时如果我们不break继续用下一个更大的素数primes[j1]去筛i * primes[j1]会发生什么因为primes[j]是i的最小质因子所以primes[j]也必然是i * primes[j1]的最小质因子。这个合数本应该由primes[j]在未来的某个轮次当i增长到(i * primes[j1]) / primes[j]时筛掉。如果现在用primes[j1]筛了那么这个合数就被一个非最小质因子筛掉了违反了“每个合数只被最小质因子筛一次”的原则算法就不再是线性的。因此必须在此时break保证逻辑正确。2.3 在线性筛过程中递推欧拉函数现在我们把线性筛和欧拉函数结合起来。目标是在筛出素数和合数的同时计算出phi[i]。我们考虑在筛掉合数t i * primes[j]的时刻如何由已知的phi[i]推导出phi[t]。这里需要分两种情况讨论这正是模板代码中if判断的逻辑来源情况一primes[j]是i的质因子即i % primes[j] 0。这意味着primes[j]已经在i的质因数集合里了。设i的质因数分解中包含primes[j]^k。 根据欧拉函数公式φ(i) i * Π(1 - 1/p)。 那么对于t i * primes[j]它只是把primes[j]这个质因子的指数增加了1并没有引入新的质因子。 因此φ(t) t * Π(1 - 1/p) (i * primes[j]) * Π(1 - 1/p) primes[j] * [i * Π(1 - 1/p)] primes[j] * φ(i)。推导公式phi[t] primes[j] * phi[i];情况二primes[j]不是i的质因子即i % primes[j] ! 0。这意味着primes[j]是一个与i互质的新质因子。 由于欧拉函数是积性函数且此时gcd(i, primes[j]) 1所以有φ(t) φ(i * primes[j]) φ(i) * φ(primes[j]) φ(i) * (primes[j] - 1)。推导公式phi[t] phi[i] * (primes[j] - 1);在线性筛的主循环中我们会在标记st[t] true的同时根据上述两种情况用对应的公式计算出phi[t]的值。而对于素数i本身我们在将其加入primes列表时直接初始化phi[i] i - 1。3. 模板代码逐行精讲与实现理解了原理我们来看完整的、带有详细注释的C模板实现。这个模板是解决 AcWing 874 这类题目的直接答案。#include iostream using namespace std; typedef long long LL; // 欧拉函数前缀和可能很大用long long存储 const int N 1000010; // 根据题目数据范围设定这里示例为1e6 int primes[N], phi[N], cnt; // phi[]存储每个数的欧拉函数值 bool st[N]; LL get_eulers(int n) { phi[1] 1; // 定义 φ(1) 1这是一个约定也方便后续计算 for (int i 2; i n; i) { if (!st[i]) { // 如果i是素数 primes[cnt] i; // 加入素数表 phi[i] i - 1; // 素数的欧拉函数值为 i-1 } // 用当前已得到的素数 primes[j] 去筛合数 for (int j 0; primes[j] n / i; j) { st[primes[j] * i] true; // 标记合数 primes[j] * i if (i % primes[j] 0) { // 情况一primes[j]是i的最小质因子 phi[primes[j] * i] phi[i] * primes[j]; break; // 保证每个合数只被最小质因子筛一次 } else { // 情况二primes[j]与i互质 phi[primes[j] * i] phi[i] * (primes[j] - 1); } } } // 计算1到n所有欧拉函数值的和根据题目要求有时只需要返回phi数组 LL res 0; for (int i 1; i n; i) res phi[i]; return res; } int main() { int n; cin n; cout get_eulers(n) endl; return 0; }关键行解析与注意事项phi[1] 1;这是数论中的定义。虽然1与自身互质但小于等于1的正整数只有1所以定义为1。这个初始化很重要保证了递推起点的正确性。if (!st[i])块这个块处理素数i。首先将其加入素数表然后根据定义直接设置phi[i] i - 1。注意phi[i]在此时已经被正确计算并存储。内层for循环这是线性筛的核心也是递推欧拉函数的核心。st[primes[j] * i] true;标记合数。务必注意这一行必须在if判断之前执行。因为无论哪种情况合数都需要被标记。if (i % primes[j] 0) {... break;}这就是之前分析的情况一。计算出phi后立即break是保证线性时间复杂度的关键操作绝对不能省略或调换顺序。else {...}对应情况二。数组大小N必须根据题目要求的n的最大值来设定通常需要比n稍大一点例如N n 10。数组开小了会导致运行时错误如段错误。结果类型LL当n较大时如1e6欧拉函数前缀和很容易超出int范围使用long long是安全的做法。4. 实战应用不止于模板如何应对变形题目掌握了模板相当于有了“锤子”。但题目不会总是“钉子”。下面我们看看如何运用这个模板和思想解决一些常见的变形问题。4.1 计算单个大数的欧拉函数有时题目不是求1到n的所有值而是求一个特定的、可能很大的数n比如n 10^12的φ(n)。这时线性筛法就不适用了因为无法开出那么大的数组。解决方案质因数分解。根据公式φ(n) n * Π(1 - 1/p)我们只需要找到n的所有不同质因子p即可。这可以通过试除法在O(sqrt(n))内完成。LL phi_single(LL n) { LL res n; for (LL i 2; i n / i; i) { if (n % i 0) { res res / i * (i - 1); // 先除后乘防止溢出 while (n % i 0) n / i; } } if (n 1) res res / n * (n - 1); // 处理剩余的大于sqrt(n)的质因子 return res; }注意计算res / i * (i - 1)而不是res * (i - 1) / i是为了保证整除避免引入浮点数。4.2 需要频繁查询区间内多个数的欧拉函数如果题目是多次查询不同n的φ(n)或者查询[a, b]区间内每个数的φ值而a和b的范围很大比如1 a b 10^12但区间长度b-a1可以接受比如 10^6该怎么办解决方案区间筛法思想。我们无法筛到10^12但可以筛出sqrt(b)以内的所有素数这很容易做到。然后利用这些素数去筛掉区间[a, b]内的合数并在筛的过程中通过类似线性筛的递推思想计算出区间内每个数的欧拉函数近似值最后再通过质因数分解微调。这是一个更高级的技巧核心是利用了“一个合数n必然有一个不大于sqrt(n)的质因子”这一性质。4.3 与欧拉函数相关的其他数论问题欧拉函数是数论中的基石很多问题都与之相关欧拉定理若gcd(a, n) 1则a^(φ(n)) ≡ 1 (mod n)。这是RSA加密算法的理论基础之一。费马小定理当n为素数p时φ(p)p-1欧拉定理退化为a^(p-1) ≡ 1 (mod p)。原根模n的原根存在的充要条件是n2, 4, p^k, 2p^kp为奇素数而原根的个数为φ(φ(n))。莫比乌斯反演欧拉函数可以通过莫比乌斯函数表示φ(n) Σ_{d|n} d * μ(n/d)。当题目涉及这些更深层的数论关系时快速计算1到n的欧拉函数值即我们的模板往往是预处理的第一步。5. 常见“坑点”与调试技巧即便理解了原理手写模板时也难免出错。下面是我在多次实现和调试中总结的几个常见坑点。5.1 数组越界与初始化坑点1primes[j] n / i这个循环条件写错。写成primes[j] n或primes[j] * i n在逻辑上似乎也对但前者会导致j可能超出cnt的范围访问primes[cnt]后者在i和primes[j]很大时可能导致primes[j] * i溢出int范围。primes[j] n / i是既安全又高效的写法。坑点2phi数组未初始化phi[1] 1。如果n1主函数中求和循环从i1开始若phi[1]是随机值结果就错了。这是一个边界条件必须处理。坑点3数组N开得不够大。这是最致命的运行时错误。务必根据题目数据范围的上限来定义N。例如题目说n 10^6那么const int N 1000010;是稳妥的。5.2 逻辑顺序与细节坑点4st[primes[j] * i] true;的位置放错。必须放在if (i % primes[j] 0)判断之前。因为无论是否break合数都需要被标记。如果放在if-else块内部在某些情况下会导致合数未被标记。坑点5忘记了break;语句。这是将算法从O(n)退化成近似O(n log log n)甚至更差的“罪魁祸首”。少了它算法虽然结果可能正确但效率大打折扣在大数据量下必然超时。坑点6结果溢出。使用int存储前缀和res。对于n1e6φ(n)的平均值约为n * 6/π^2 ≈ 0.6079n总和大约为0.6 * n^2 / 2对于n1e6这远远超过了int的表示范围约21亿。必须用long long。5.3 调试方法当程序输出错误结果时可以按以下步骤排查小数据测试用n10或n20这样的小数据手动计算欧拉函数值与程序输出的phi数组逐项对比。这是最直接有效的方法。打印中间变量在循环中打印i,primes[j],primes[j]*i,phi[primes[j]*i]的值观察递推过程是否符合两种情况的公式。检查素数表单独运行线性筛函数打印primes数组检查素数是否正确生成。如果素数表错了后面的欧拉函数计算肯定全错。检查边界单独测试n1的情况。6. 从模板到理解如何内化这个算法死记硬背模板应付一道题是简单的但真正掌握它才能应对变化。我建议的学习路径是理解第一记忆第二务必搞懂欧拉函数的积性、线性筛的break条件、以及两种递推情况的数学推导。自己能在白板上推导出phi[t] phi[i] * primes[j]和phi[t] phi[i] * (primes[j] - 1)这两个公式才算真正理解。亲手实现关掉参考自己从头敲一遍代码。遇到卡壳的地方回去看原理。反复几次直到能流畅地、无错误地写出来。尝试变形用这个模板的思想去尝试实现“线性筛求莫比乌斯函数μ(n)”或者“线性筛求约数个数d(n)”。你会发现它们的结构惊人地相似只是递推公式不同。这能极大地加深你对“积性函数线性筛”这个通用范式的理解。对比学习将线性筛求欧拉函数与埃氏筛求欧拉函数的代码进行对比。埃氏筛版本通常更简短但时间复杂度是O(n log log n)且对于每个合数会重复计算多次。理解两者的效率差异和适用场景。最后这个模板的价值不仅在于解决“求欧拉函数前缀和”这一道题更在于它提供了一种高效处理数论积性函数前缀和的经典范式。当你遇到需要快速计算莫比乌斯函数前缀和、约数和函数前缀和等问题时你会感谢现在深入理解了这个模板的自己。在算法竞赛和数论学习中它是一把打开许多大门的钥匙。