1. 项目概述线性筛与欧拉函数的效率融合在算法竞赛和数论编程中我们经常遇到一个经典问题如何高效地求出从1到NN可能非常大比如10^7每个数的欧拉函数值如果你尝试对每个数单独用公式φ(n)n∏(1-1/p)去分解质因数计算当N很大时时间复杂度会变得难以接受。这时“线性筛法求欧拉函数”就成为了一个必须掌握的利器。它巧妙地将线性时间复杂度的素数筛法欧拉筛与欧拉函数的递推性质结合起来能在O(N)的时间内一次性计算出所有欧拉函数值效率极高。这个模板题的核心价值在于它不仅仅是一个数学公式的代码实现更是一种“预处理”思想的典范。通过一次线性的预处理我们将后续所有关于区间内欧拉函数的查询都降到了O(1)的常数时间。无论是解决需要频繁调用欧拉函数的数论问题还是作为更复杂算法如莫比乌斯反演的组成部分这个模板都扮演着基石的角色。接下来我将从原理到实现细节一步步拆解这个高效的算法并分享我在实际编码和调试中积累的经验与避坑指南。2. 核心原理深度解析线性筛为何能同步求φ2.1 欧拉函数的定义与基础性质欧拉函数φ(n)表示的是小于等于n的正整数中与n互质的数的个数。它的计算公式基于n的质因数分解若n p1^k1 * p2^k2 * ... * pm^km则 φ(n) n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pm)。这个公式直观地反映了“互质”的概率意义。对于我们的线性筛算法最关键的是欧拉函数的以下两个递推性质当p是质数时φ(p) p - 1。这很好理解因为对于一个质数p1到p-1的所有数都与其互质。积性函数性质如果a和b互质gcd(a, b)1那么φ(a*b) φ(a) * φ(b)。这个性质是线性筛能够工作的理论基础。然而在线性筛的过程中我们处理的并不总是互质的两个数。核心技巧在于处理当筛到的合数i * primes[j]其最小质因子primes[j]整除i时的特殊情况。这时我们需要另一个递推公式。2.2 线性筛欧拉筛的运作机制回顾线性筛之所以是“线性”是因为它保证了每个合数只会被其最小质因子筛掉一次。这是通过一个关键的判断条件实现的if (i % primes[j] 0) break;。算法的流程大致如下维护一个布尔数组st[N]标记是否为合数一个数组primes[]存放已找到的质数。外层循环i从2遍历到N。如果i是质数!st[i]则加入primes数组。内层循环遍历当前的质数表primes[j]标记合数st[i * primes[j]] true。关键步骤一旦发现primes[j]是i的质因子i % primes[j] 0就立即跳出内层循环。这保证了primes[j]始终是i * primes[j]的最小质因子并且每个合数只被标记一次。2.3 在线性筛中递推欧拉函数现在我们将欧拉函数的计算嵌入到这个筛法框架中。我们额外维护一个数组phi[N]来存储每个数的欧拉函数值。我们需要根据i和当前质数primes[j]的关系分两种情况推导phi[i * primes[j]]情况一primes[j]是i的质因子即i % primes[j] 0此时primes[j]是i的质因子也必然是i * primes[j]的质因子。设n i * primes[j]。 由于primes[j]已经在i的质因数集合里根据欧拉函数公式 φ(n) n * ∏(1 - 1/p) (i * primes[j]) * ∏(1 - 1/p)其中连乘积部分与i的完全相同。 因此φ(i * primes[j]) primes[j] * [ i * ∏(1 - 1/p) ] primes[j] * φ(i)。推导公式phi[i * primes[j]] primes[j] * phi[i];情况二primes[j]不是i的质因子即i % primes[j] ! 0此时primes[j]是一个与i互质的质数。根据欧拉函数的积性性质 φ(i * primes[j]) φ(i) * φ(primes[j])。 而φ(primes[j]) primes[j] - 1。推导公式phi[i * primes[j]] phi[i] * (primes[j] - 1);这样在筛法进行的同时我们就能利用已知的phi[i]和phi[primes[j]]或primes[j]-1来递推求出新的phi值。初始化时我们定义phi[1] 1虽然通常φ(1)1且1与任何数互质这里作为递推起点。注意这里有一个初学者容易混淆的点。phi[1]1的设定主要是为了在情况二primes[j]与i互质时当i1公式phi[1 * primes[j]] phi[1] * (primes[j] - 1)能够正确计算出质数的欧拉函数值primes[j]-1。它是一个逻辑上的起点并非直接来自φ(1)的数学定义虽然结果巧合相同。在实际编码中我们通常从i2开始循环并单独处理质数的φ值。3. 代码实现与逐行精讲理解了原理我们来看C的模板实现。我将提供一个清晰、完整且带有详细注释的版本。#include iostream #include algorithm using namespace std; typedef long long LL; // 欧拉函数值和最终总和可能很大使用long long const int N 1000010; // 根据题目数据范围设定这里示例为1e6 int primes[N], cnt; // primes[]存储所有素数cnt是素数个数 int phi[N]; // phi[]存储每个数的欧拉函数值 bool st[N]; // st[x]存储x是否被筛掉是否为合数 LL get_eulers(int n) { phi[1] 1; // 初始化定义phi[1] 1 for (int i 2; i n; i ) { if (!st[i]) { // 如果i是素数 primes[cnt ] i; // 将i加入素数数组 phi[i] i - 1; // 素数的欧拉函数值为 i - 1 } // 用当前已得到的素数去筛掉以i为最大因子的合数 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; // 保证每个合数只被其最小质因子筛掉 } // 情况二primes[j]不是i的质因子 phi[primes[j] * i] phi[i] * (primes[j] - 1); } } // 计算1到n所有欧拉函数值的和根据题目要求模板题通常要求求和 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; }3.1 关键代码段解析数组大小与类型const int N需要根据题目数据范围设定。phi数组和结果res必须使用long long这里用typedef LL因为欧拉函数值之和很容易超出int范围。例如n10^6时总和已经远超21亿。初始化phi[1] 1如前所述这是递推的逻辑起点确保后续计算正确。质数判断与初始化if (!st[i])判断i为质数后执行phi[i] i - 1。这是欧拉函数对质数的定义。内层循环条件primes[j] n / i。这是防止primes[j] * i溢出的经典写法比primes[j] * i n更安全。核心递推逻辑st[primes[j] * i] true;标记合数这是筛法的本职工作。if (i % primes[j] 0) {... break;}这是线性筛的灵魂也是欧拉函数递推的分水岭。当条件成立根据情况一公式计算phi然后break。这个break至关重要它保证了线性时间复杂度。当条件不成立根据情况二公式计算phi。结果求和模板题通常要求输出1到n所有φ(n)的和。我们可以在筛法完成后线性遍历phi数组累加。3.2 内存与效率优化思考对于极端大的N比如接近10^7我们需要关注内存占用。这个算法需要三个大小为N的数组st,phi,primes。其中st可以用bitsetN来替代bool数组能将内存消耗减少到约1/8。primes数组的大小约为N/ln(N)可以精确估算以节省空间。但在大多数竞赛场景中直接开bool数组是简单可靠的选择。实操心得在时间紧迫的竞赛中我通常先采用这个清晰的标准模板。只有在内存限制特别严格如N很大且内存很小时才会考虑用bitset。过早优化有时会引入额外的复杂度和调试时间。4. 模板的变通与应用场景这个模板不仅用于求和其产出的phi[]数组本身就是一个强大的预处理工具。4.1 解决单点查询问题如果问题不是求和而是多次询问某个数x的φ(x)我们可以在主函数中调用一次get_eulers(MAX_N)进行全局预处理之后每次询问都可以用O(1)的时间通过phi[x]直接得到答案。这比每次单独计算要高效无数倍。// 预处理 get_eulers(1000000); // 回答Q次询问 while (Q--) { int x; cin x; cout phi[x] endl; }4.2 作为其他数论算法的组件欧拉函数是许多高级数论算法的基础。例如莫比乌斯反演线性筛同样可以求莫比乌斯函数μ(n)其代码结构与筛法求欧拉函数极其相似。原根判定一个数m有原根的充要条件是m2,4,p^k,2p^kp为奇素数而原根的个数是φ(φ(m))。模n既约剩余系与n互质的φ(n)个数构成一个乘法群欧拉函数给出了这个群的大小。掌握这个线性筛求欧拉函数的模板相当于打通了学习这些更深入数论知识的第一道关卡。5. 常见错误与调试技巧实录即使理解了原理实现时也难免踩坑。下面是我在学习和教学过程中总结的常见问题。5.1 典型错误列表错误现象可能原因解决方案输出结果错误比正确答案小1.phi[1]未初始化为1。2. 结果res或phi数组使用了int类型导致溢出。3. 内层循环条件写成了primes[j] * i n在i和primes[j]较大时可能溢出。1. 检查phi[1]1。2. 将res和phi数组改为long long。3. 将循环条件改为primes[j] n / i。输出结果错误杂乱无章递推公式用错。最常见的是混淆了情况一和情况二的公式。牢记判断条件i % primes[j] 0。成立时phi phi[i] * primes[j]。不成立时phi phi[i] * (primes[j] - 1)。程序运行超时TLE忘记了内层循环中的break语句。这会导致每个合数被多次标记算法退化为近似O(N log log N)的埃氏筛在N很大时超时。确保在if (i % primes[j] 0)执行phi计算后立刻break。程序内存超限MLE数组N开得过大或者使用了bool数组但N极大如1e8。1. 精确评估题目数据范围。2. 考虑使用bitset替代bool数组。质数表primes越界cnt可能超过primes数组的初始分配大小。primes大小应至少为N/ln(N) 10。安全起见primes数组大小可以直接开成N或者精确估算。5.2 调试与验证技巧小数据验证首先用n10这样的小数据手动计算并与程序输出对比。打印出phi[]数组的每一个值检查是否正确。φ(1)1, φ(2)1, φ(3)2, φ(4)2, φ(5)4, φ(6)2, φ(7)6, φ(8)4, φ(9)6, φ(10)4。总和应为112242646432。单独测试筛法如果不确定欧拉函数部分是否正确可以先注释掉phi相关的计算只运行线性筛质数的部分验证primes数组是否正确。关注溢出对于n较大的测试重点检查数据类型。计算一下理论最大值φ(n) ≤ n前n个φ值之和小于n^2。当n1e6时n^21e12远超int范围必须用long long。使用标准序列对照OEIS整数序列在线百科全书上有欧拉函数φ(n)的序列A000010和前n项和的序列A002088。可以用已知的正确序列来验证程序输出。6. 性能分析与扩展对比6.1 时间复杂度分析算法主体是两个嵌套循环但得益于那个关键的break每个合数仅被其最小质因子标记一次。因此标记合数的操作总共执行了大约N次等于1到N之间合数的数量。计算欧拉函数值的操作与标记操作一一对应也是O(N)次。所以整体时间复杂度是严格的O(N)线性级别。6.2 与其他求欧拉函数方法的对比方法时间复杂度 (求1~n所有φ)空间复杂度适用场景线性筛法本文O(N)O(N)最优选择。需要预处理1~n所有φ值或需要频繁查询。对每个数单独质因数分解O(N√N)O(1)仅需计算极少几个数的φ值且n本身不大。埃氏筛改进版O(N log log N)O(N)比线性筛稍慢但代码更简单在N极大且时限宽松时可考虑。利用公式φ(n)n∏(1-1/p)直接计算O(√n) per queryO(1)单次查询n巨大但查询次数极少。显然当需要处理区间内大量欧拉函数信息时线性筛法是压倒性的最优解。6.3 扩展同步求多个积性函数线性筛的强大之处在于其框架可以同时求出多个积性函数。除了欧拉函数φ(n)常见的还有约数个数函数d(n)表示n的正约数个数。约数和函数σ(n)表示n的所有正约数之和。莫比乌斯函数μ(n)。它们的递推公式在线性筛的两种情况下也都有定义。例如求约数个数时需要额外记录每个数的最小质因子的次数。这体现了线性筛作为一个“积性函数生成器”的通用性。掌握求φ(n)的模板后尝试修改代码同步计算其他函数是对这个算法框架更深层次的理解。最后记住这个模板的关键利用最小质因子筛数的时机根据质因子是否整除当前数应用不同的积性函数递推公式。多写几遍多调试几次它就会成为你解决数论预处理问题时信手拈来的工具。在竞赛中遇到涉及1到N范围内数论函数求和或查询的问题第一个想到的就应该是线性筛预处理。