1. 项目背景与核心价值在算法竞赛和日常开发中我们常常会遇到需要快速计算一个范围内所有数的欧拉函数Euler‘s Totient Function的场景。比如在解决某些数论问题、RSA加密算法的原理理解或者需要处理大量与互质相关的计数问题时直接对每个数进行质因数分解来求欧拉函数时间复杂度是O(n√n)当n达到百万甚至千万级别时这几乎是不可接受的。这时筛法Sieve的价值就凸显出来了。Acwing 874题“筛法求欧拉函数”正是这样一个经典的教学案例它要求我们利用线性筛法也叫欧拉筛的思想在O(n)的时间复杂度内一次性计算出1到n所有数的欧拉函数值。很多初学者包括当年的我在学习数论筛法时容易把“筛法求素数”、“筛法求欧拉函数”、“筛法求莫比乌斯函数”这几个概念混淆或者孤立地学习。实际上它们的核心骨架——线性筛——是相通的。理解了这个骨架你就能举一反三。本篇内容将不仅仅是一份Java的解题代码我会带你彻底拆解线性筛求欧拉函数的每一步为什么这么做从质因数分解的原始公式出发推导出筛法状态转移的数学原理并给出一个可以直接“抄作业”的、经过实战检验的Java模板。同时我们会深入探讨几个关键细节如何避免整数溢出、如何处理边界条件、以及这个模板与“分解质因数求单个欧拉函数”模板之间的内在联系与选择策略。无论你是正在刷Acwing算法基础课还是在准备面试中可能遇到的数论问题这篇内容都将为你提供一个坚实的、可复现的解决方案。2. 从质因数分解到筛法欧拉函数的两种求法在深入筛法之前我们必须夯实基础理解欧拉函数的定义和它的原始计算方法。欧拉函数 φ(n) 表示的是小于等于n的正整数中与n互质的数的个数。例如φ(8)4因为1,3,5,7这4个数与8互质。它的计算公式正是通过质因数分解得到的若 n p1^a1 * p2^a2 * ... * pk^ak其中pi是质数则 φ(n) n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk)。这个公式是推导筛法的基石。基于这个公式我们有最直接的两种计算单个数φ(n)的方法方法一直接质因数分解。这是最直观的方法。对于一个数n我们找出它所有的质因数然后套用公式。在Java中这通常需要一个循环从2遍历到√n。public static int phi(int x) { int res x; for (int i 2; i x / i; i) { if (x % i 0) { res res / i * (i - 1); // 注意计算顺序先除后乘防溢出 while (x % i 0) x / i; } } if (x 1) res res / x * (x - 1); return res; }这里有个关键技巧res res / i * (i - 1)。为什么不写成res res * (i - 1) / i因为后者可能造成中间结果溢出整数范围。先进行除法运算可以保证值始终在可控范围内这是一个非常实用的防溢出技巧。方法二埃氏筛Eratosthenes改进版。我们可以利用一个数组phi[]初始化phi[i] i。然后遍历所有质数p对于p的所有倍数j执行phi[j] phi[j] / p * (p - 1)。这个方法的时间复杂度大约是O(n log log n)比方法一求n个数要快但还不是最优。那么为什么我们还需要线性筛因为当题目要求我们输出1到n每一个数的欧拉函数时方法一的总复杂度是O(n√n)方法二的复杂度是O(n log log n)。而线性筛可以将复杂度降至严格的O(n)在n很大时优势巨大。更重要的是线性筛的过程体现了动态规划的思想它基于每个数最小的质因数来进行状态转移这个思想在求其他积性函数时也是通用的。接下来我们就进入核心部分。3. 线性筛求欧拉函数的原理与状态转移推导线性筛又称欧拉筛它的核心目标是确保每个合数只被其最小的质因数筛掉一次。我们使用一个数组primes[]存储已发现的质数一个数组st[]标记某个数是否被筛过。在筛质数的过程中当我们遍历到每个数i时无论i是质数还是合数我们都用已知的质数primes[j]去尝试筛掉i * primes[j]。关键在于当i % primes[j] 0时我们必须停下因为此时primes[j]是i的最小质因数也必然是i * primes[j]的最小质因数。如果继续用更大的质数去筛就会导致i * primes[j]这个数被重复筛除。现在我们要在这个筛骨架上同时计算欧拉函数phi[]。我们需要找到phi[i * primes[j]]和已知的phi[i]或phi[primes[j]]之间的关系。这里分为两种情况这正是理解整个算法的关键情况1primes[j]是i的质因数即i % primes[j] 0。设i primes[j]^k * m其中m与primes[j]互质。 那么n i * primes[j] primes[j]^(k1) * m。 根据欧拉函数公式φ(i) i * (1 - 1/primes[j]) * Π_{p|m}(1 - 1/p)φ(n) n * (1 - 1/primes[j]) * Π_{p|m}(1 - 1/p)仔细观察你会发现两个公式中(1 - 1/primes[j]) * Π_{p|m}(1 - 1/p)这一部分是完全相同的因此我们可以得到φ(n) n * (φ(i) / i) primes[j] * i * (φ(i) / i) primes[j] * φ(i)所以当i % primes[j] 0时φ(i * primes[j]) primes[j] * φ(i)。情况2primes[j]不是i的质因数即i % primes[j] ! 0。这意味着primes[j]是一个与i互质的新质数。 那么n i * primes[j]且gcd(i, primes[j]) 1。 根据欧拉函数是积性函数的性质当两个数互质时其欧拉函数值的乘积等于它们乘积的欧拉函数值我们有φ(n) φ(i) * φ(primes[j])而φ(primes[j]) primes[j] - 1因为质数与小于它的所有正整数都互质。 所以当i % primes[j] ! 0时φ(i * primes[j]) φ(i) * (primes[j] - 1)。这两个递推公式就是我们在筛法过程中动态维护phi[]数组的全部依据。整个算法在O(n)的线性时间内同步完成了质数筛选和欧拉函数计算两件事。4. Java模板代码逐行精讲与避坑指南理解了数学原理我们来看Java实现。下面这个模板是经过多次ACwing提交验证的包含了所有必要的细节处理。import java.util.Scanner; public class Main { static final int N 1000010; // 根据题目数据范围设定这里假设n最大为1e6 static int[] primes new int[N]; // 存储所有筛选出来的质数 static int cnt; // 质数的个数 static int[] phi new int[N]; // 存储每个数的欧拉函数值 static boolean[] st new boolean[N]; // 标记是否被筛掉true表示不是质数 public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); getEulers(n); long res 0; // 注意这里用long因为1到n的欧拉函数和可能超出int范围 for (int i 1; i n; i) { res phi[i]; } System.out.println(res); } static void getEulers(int n) { phi[1] 1; // 初始化1的欧拉函数定义为1 for (int i 2; i n; i) { if (!st[i]) { // 如果i没有被筛掉那么i是质数 primes[cnt] i; // 将质数i存入数组 phi[i] i - 1; // 质数i的欧拉函数值为 i-1 } // 用当前已得到的质数primes[j]去筛掉i * primes[j] for (int j 0; primes[j] n / i; j) { // 防溢出条件primes[j] n / i st[primes[j] * i] true; // 标记合数 if (i % primes[j] 0) { // 情况1primes[j]是i的最小质因子 phi[primes[j] * i] phi[i] * primes[j]; break; // 核心保证每个数只被最小质因子筛一次 } else { // 情况2primes[j]与i互质 phi[primes[j] * i] phi[i] * (primes[j] - 1); } } } } }现在我们来逐行分析关键点和避坑指南数组大小N这是第一个坑。必须根据题目数据范围开足够大的数组。Acwing 874题中n最大是10^6所以N至少为1000010。如果你在本地测试没问题但提交报ArrayIndexOutOfBounds首先检查这里。phi[1] 1这是一个定义。在数论中φ(1)通常被定义为1。虽然1与1互质但根据公式计算有些争议直接记住并初始化即可。忘记初始化会导致求和错误。质数的欧拉函数当i是质数时phi[i] i - 1。这是由定义直接得出的所有小于i的正整数都与i互质。循环条件primes[j] n / i这是防止整数溢出的生命线。判断条件不能写成primes[j] * i n因为当i和primes[j]都很大时它们的乘积可能超过int甚至long的范围导致计算溢出循环条件判断错误。而primes[j] n / i利用了整除在判断阶段就避免了乘法运算是标准的防溢出写法。状态转移与break这是线性筛的灵魂。if (i % primes[j] 0)分支对应原理推导的情况1计算后立即break。break的原因此时primes[j]已是i的最小质因数。对于后续更大的质数primes[j1]primes[j1] * i这个合数的最小质因数应该是primes[j]而不是primes[j1]。如果不用break这个数会在后面当i变大到某个值时再次被primes[j]筛掉这就造成了重复标记破坏了线性复杂度。else分支对应情况2。结果累加用long这是第二个大坑。题目往往要求输出1到n所有欧拉函数的和。当n较大时这个和很容易超过32位int的表示范围约21亿。例如n10^6时总和已经很大。因此用于累加的变量res必须使用long类型。函数命名与封装将核心筛法过程封装在getEulers(int n)方法中是一个好习惯使主逻辑清晰也便于调试和复用。5. 模板的变通如何应对不同场景需求上面给出的模板是“计算1到n所有欧拉函数值并求和”的完整解决方案。但在实际做题或面试中问题可能会稍有变化我们需要灵活调整。场景一只需要计算单个数的欧拉函数但需要多次查询。如果题目是给你多个n每次询问φ(n)。这时预处理1到最大范围N的所有φ值每次查询就是O(1)的复杂度。我们的模板完全适用只需在main函数中调用一次getEulers(N)之后直接读取phi[x]即可。这体现了“空间换时间”的思想。场景二只需要判断或使用质数同时需要欧拉函数。我们的模板在筛出质数列表primes的同时也求得了phi。如果你的问题需要同时用到这两个信息这个模板就一举两得了。场景三数据范围极大例如n10^7或更大内存紧张。我们的模板使用了三个O(n)的数组primes,phi,st。当n非常大时这可能占用上百MB内存。此时可以考虑使用BitSet替代boolean[] st来节省空间因为BitSet内部按位存储。但需要注意BitSet的访问和设置比数组稍慢在时间允许的情况下可以考虑。// 使用BitSet的示例 import java.util.BitSet; BitSet st new BitSet(N); ... if (!st.get(i)) { ... } st.set(primes[j] * i);场景四分解质因数模板与筛法模板的选择。这是初学者常问的问题。如何选择使用分解质因数模板本文第2节方法一的情况只需要计算单个或极少数数的欧拉函数。数字n本身非常大但需要计算φ(n)此时无法预处理那么大的范围。面试中面试官明确要求展示质因数分解的能力。使用线性筛模板的情况需要计算一个连续区间内所有数的欧拉函数。需要频繁查询不同n的φ(n)且n的范围在可预处理之内。问题本身就需要用到质数表或线性筛的框架。简单来说“少量单点查询用分解大量区间预处理用筛法”。6. 典型错误分析与调试技巧即便理解了原理和模板亲手实现时还是可能遇到各种问题。下面我列举几个我踩过的坑和调试方法错误1结果输出为0或负数。可能原因1累加和res使用了int类型发生溢出。解决务必使用long。可能原因2phi[]数组没有正确初始化特别是phi[1]。确保getEulers函数中第一行是phi[1] 1。可能原因3循环边界错误。检查getEulers中的for (int i 2; i n; i)和for (int j 0; primes[j] n / i; j)。后者是核心确保j cnt的条件隐含在primes[j] n / i中因为质数数组是递增的当primes[j]太大时条件不满足循环自然结束。错误2运行超时TLE。可能原因没有正确break导致算法退化为O(n^2)的复杂度。仔细检查在if (i % primes[j] 0)分支中计算完phi后是否立即break。检查方法可以写一个简单的测试输入n10^6观察程序运行时间。线性筛应该在毫秒级完成。如果很慢几乎可以肯定是break逻辑有问题。错误3数组越界ArrayIndexOutOfBounds。可能原因1静态数组primes开得太小。线性筛中质数个数大约是n / log(n)对于n10^6质数个数约7.8万。primes数组大小应略大于这个值通常直接开和N一样大是安全的。可能原因2在primes[j] n / i这个条件中当j等于质数数组的实际长度cnt时primes[j]会越界。我们的写法之所以正确是因为当j增长到cnt时primes[j]是0int数组默认值0 n/i这个条件对于正数n/i通常为false除非n/i也为0但这不可能循环终止。这是一种简洁的写法。更安全的写法是加上j cnt的条件for (int j 0; j cnt primes[j] n / i; j)。调试技巧小数据验证不要一上来就用大数据测试。用n10, 20这样的小数据手动计算出每个数的欧拉函数然后打印出程序计算的phi[]数组进行对比。打印中间变量在getEulers循环中打印出i,primes[j],phi[i * primes[j]]的值观察状态转移是否符合我们推导的两种情况。专注边界特别注意i1 i质数以及i%primes[j]0的第一个时刻例如i4, primes[j]2这些边界点的逻辑是否正确。7. 举一反三线性筛框架的其他应用掌握线性筛求欧拉函数真正的价值在于你学会了一个强大的框架。这个框架可以用于计算其他常见的积性函数。所谓积性函数就是对于任意互质的正整数a, b满足f(a*b) f(a) * f(b)的函数。欧拉函数φ(n)就是积性函数。例子1求莫比乌斯函数 μ(n)。莫比乌斯函数的定义是μ(1) 1若n含有平方因子则μ(n)0若n是k个不同质数的乘积则μ(n)(-1)^k在线性筛中我们可以这样维护if (!st[i]) { primes[cnt] i; mu[i] -1; // 单个质数k1 (-1)^1 -1 } for (int j0; primes[j]n/i; j) { st[primes[j]*i] true; if (i % primes[j] 0) { mu[primes[j]*i] 0; // i包含primes[j]的平方因子 break; } else { mu[primes[j]*i] -mu[i]; // 多了一个新的不同质因子符号取反 } }例子2求约数个数函数 d(n)。设n p1^a1 * p2^a2 * ... * pk^ak则d(n) (a11)(a21)...*(ak1)。 我们需要额外维护一个数组minp[]或a[]记录每个数最小质因子的指数。// 假设 num[i] 记录i的约数个数 minp[i]记录i的最小质因子的指数1 if (!st[i]) { primes[cnt] i; num[i] 2; // 质数只有1和自身两个约数 minp[i] 1; // 指数为1所以1后为2 } for (int j0; primes[j]n/i; j) { st[primes[j]*i] true; if (i % primes[j] 0) { minp[primes[j]*i] minp[i] 1; // 最小质因子指数增加1 num[primes[j]*i] num[i] / minp[i] * (minp[i] 1); // 更新约数个数 break; } else { minp[primes[j]*i] 1; // 新的最小质因子指数为1 num[primes[j]*i] num[i] * 2; // 约数个数翻倍乘(11) } }看到这里你会发现模式是高度一致的在i % primes[j] 0的break分支处理最小质因子次数增加的情况在else分支处理新增一个互质质因子的情况。理解了这个模式你就能用线性筛框架解决一大类数论函数前缀和的问题。最后我个人的一点体会是学习算法模板切忌死记硬背。一定要像我们今天这样把背后的数学推导和状态转移关系弄明白。当初我学习时就是亲手把phi[i * primes[j]]的两种情况的公式推导了好几遍直到它变成一种直觉。下次当你需要用到“筛法求欧拉函数”时希望你能直接回忆起“互质就乘(p-1)不互质即整除就乘p”这个核心口诀并能够自己重新推导出完整的代码。这才是真正掌握了这个知识。 线性筛法求欧拉函数：原理、Java实现与工程实践
1. 项目背景与核心价值在算法竞赛和日常开发中我们常常会遇到需要快速计算一个范围内所有数的欧拉函数Euler‘s Totient Function的场景。比如在解决某些数论问题、RSA加密算法的原理理解或者需要处理大量与互质相关的计数问题时直接对每个数进行质因数分解来求欧拉函数时间复杂度是O(n√n)当n达到百万甚至千万级别时这几乎是不可接受的。这时筛法Sieve的价值就凸显出来了。Acwing 874题“筛法求欧拉函数”正是这样一个经典的教学案例它要求我们利用线性筛法也叫欧拉筛的思想在O(n)的时间复杂度内一次性计算出1到n所有数的欧拉函数值。很多初学者包括当年的我在学习数论筛法时容易把“筛法求素数”、“筛法求欧拉函数”、“筛法求莫比乌斯函数”这几个概念混淆或者孤立地学习。实际上它们的核心骨架——线性筛——是相通的。理解了这个骨架你就能举一反三。本篇内容将不仅仅是一份Java的解题代码我会带你彻底拆解线性筛求欧拉函数的每一步为什么这么做从质因数分解的原始公式出发推导出筛法状态转移的数学原理并给出一个可以直接“抄作业”的、经过实战检验的Java模板。同时我们会深入探讨几个关键细节如何避免整数溢出、如何处理边界条件、以及这个模板与“分解质因数求单个欧拉函数”模板之间的内在联系与选择策略。无论你是正在刷Acwing算法基础课还是在准备面试中可能遇到的数论问题这篇内容都将为你提供一个坚实的、可复现的解决方案。2. 从质因数分解到筛法欧拉函数的两种求法在深入筛法之前我们必须夯实基础理解欧拉函数的定义和它的原始计算方法。欧拉函数 φ(n) 表示的是小于等于n的正整数中与n互质的数的个数。例如φ(8)4因为1,3,5,7这4个数与8互质。它的计算公式正是通过质因数分解得到的若 n p1^a1 * p2^a2 * ... * pk^ak其中pi是质数则 φ(n) n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk)。这个公式是推导筛法的基石。基于这个公式我们有最直接的两种计算单个数φ(n)的方法方法一直接质因数分解。这是最直观的方法。对于一个数n我们找出它所有的质因数然后套用公式。在Java中这通常需要一个循环从2遍历到√n。public static int phi(int x) { int res x; for (int i 2; i x / i; i) { if (x % i 0) { res res / i * (i - 1); // 注意计算顺序先除后乘防溢出 while (x % i 0) x / i; } } if (x 1) res res / x * (x - 1); return res; }这里有个关键技巧res res / i * (i - 1)。为什么不写成res res * (i - 1) / i因为后者可能造成中间结果溢出整数范围。先进行除法运算可以保证值始终在可控范围内这是一个非常实用的防溢出技巧。方法二埃氏筛Eratosthenes改进版。我们可以利用一个数组phi[]初始化phi[i] i。然后遍历所有质数p对于p的所有倍数j执行phi[j] phi[j] / p * (p - 1)。这个方法的时间复杂度大约是O(n log log n)比方法一求n个数要快但还不是最优。那么为什么我们还需要线性筛因为当题目要求我们输出1到n每一个数的欧拉函数时方法一的总复杂度是O(n√n)方法二的复杂度是O(n log log n)。而线性筛可以将复杂度降至严格的O(n)在n很大时优势巨大。更重要的是线性筛的过程体现了动态规划的思想它基于每个数最小的质因数来进行状态转移这个思想在求其他积性函数时也是通用的。接下来我们就进入核心部分。3. 线性筛求欧拉函数的原理与状态转移推导线性筛又称欧拉筛它的核心目标是确保每个合数只被其最小的质因数筛掉一次。我们使用一个数组primes[]存储已发现的质数一个数组st[]标记某个数是否被筛过。在筛质数的过程中当我们遍历到每个数i时无论i是质数还是合数我们都用已知的质数primes[j]去尝试筛掉i * primes[j]。关键在于当i % primes[j] 0时我们必须停下因为此时primes[j]是i的最小质因数也必然是i * primes[j]的最小质因数。如果继续用更大的质数去筛就会导致i * primes[j]这个数被重复筛除。现在我们要在这个筛骨架上同时计算欧拉函数phi[]。我们需要找到phi[i * primes[j]]和已知的phi[i]或phi[primes[j]]之间的关系。这里分为两种情况这正是理解整个算法的关键情况1primes[j]是i的质因数即i % primes[j] 0。设i primes[j]^k * m其中m与primes[j]互质。 那么n i * primes[j] primes[j]^(k1) * m。 根据欧拉函数公式φ(i) i * (1 - 1/primes[j]) * Π_{p|m}(1 - 1/p)φ(n) n * (1 - 1/primes[j]) * Π_{p|m}(1 - 1/p)仔细观察你会发现两个公式中(1 - 1/primes[j]) * Π_{p|m}(1 - 1/p)这一部分是完全相同的因此我们可以得到φ(n) n * (φ(i) / i) primes[j] * i * (φ(i) / i) primes[j] * φ(i)所以当i % primes[j] 0时φ(i * primes[j]) primes[j] * φ(i)。情况2primes[j]不是i的质因数即i % primes[j] ! 0。这意味着primes[j]是一个与i互质的新质数。 那么n i * primes[j]且gcd(i, primes[j]) 1。 根据欧拉函数是积性函数的性质当两个数互质时其欧拉函数值的乘积等于它们乘积的欧拉函数值我们有φ(n) φ(i) * φ(primes[j])而φ(primes[j]) primes[j] - 1因为质数与小于它的所有正整数都互质。 所以当i % primes[j] ! 0时φ(i * primes[j]) φ(i) * (primes[j] - 1)。这两个递推公式就是我们在筛法过程中动态维护phi[]数组的全部依据。整个算法在O(n)的线性时间内同步完成了质数筛选和欧拉函数计算两件事。4. Java模板代码逐行精讲与避坑指南理解了数学原理我们来看Java实现。下面这个模板是经过多次ACwing提交验证的包含了所有必要的细节处理。import java.util.Scanner; public class Main { static final int N 1000010; // 根据题目数据范围设定这里假设n最大为1e6 static int[] primes new int[N]; // 存储所有筛选出来的质数 static int cnt; // 质数的个数 static int[] phi new int[N]; // 存储每个数的欧拉函数值 static boolean[] st new boolean[N]; // 标记是否被筛掉true表示不是质数 public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); getEulers(n); long res 0; // 注意这里用long因为1到n的欧拉函数和可能超出int范围 for (int i 1; i n; i) { res phi[i]; } System.out.println(res); } static void getEulers(int n) { phi[1] 1; // 初始化1的欧拉函数定义为1 for (int i 2; i n; i) { if (!st[i]) { // 如果i没有被筛掉那么i是质数 primes[cnt] i; // 将质数i存入数组 phi[i] i - 1; // 质数i的欧拉函数值为 i-1 } // 用当前已得到的质数primes[j]去筛掉i * primes[j] for (int j 0; primes[j] n / i; j) { // 防溢出条件primes[j] n / i st[primes[j] * i] true; // 标记合数 if (i % primes[j] 0) { // 情况1primes[j]是i的最小质因子 phi[primes[j] * i] phi[i] * primes[j]; break; // 核心保证每个数只被最小质因子筛一次 } else { // 情况2primes[j]与i互质 phi[primes[j] * i] phi[i] * (primes[j] - 1); } } } } }现在我们来逐行分析关键点和避坑指南数组大小N这是第一个坑。必须根据题目数据范围开足够大的数组。Acwing 874题中n最大是10^6所以N至少为1000010。如果你在本地测试没问题但提交报ArrayIndexOutOfBounds首先检查这里。phi[1] 1这是一个定义。在数论中φ(1)通常被定义为1。虽然1与1互质但根据公式计算有些争议直接记住并初始化即可。忘记初始化会导致求和错误。质数的欧拉函数当i是质数时phi[i] i - 1。这是由定义直接得出的所有小于i的正整数都与i互质。循环条件primes[j] n / i这是防止整数溢出的生命线。判断条件不能写成primes[j] * i n因为当i和primes[j]都很大时它们的乘积可能超过int甚至long的范围导致计算溢出循环条件判断错误。而primes[j] n / i利用了整除在判断阶段就避免了乘法运算是标准的防溢出写法。状态转移与break这是线性筛的灵魂。if (i % primes[j] 0)分支对应原理推导的情况1计算后立即break。break的原因此时primes[j]已是i的最小质因数。对于后续更大的质数primes[j1]primes[j1] * i这个合数的最小质因数应该是primes[j]而不是primes[j1]。如果不用break这个数会在后面当i变大到某个值时再次被primes[j]筛掉这就造成了重复标记破坏了线性复杂度。else分支对应情况2。结果累加用long这是第二个大坑。题目往往要求输出1到n所有欧拉函数的和。当n较大时这个和很容易超过32位int的表示范围约21亿。例如n10^6时总和已经很大。因此用于累加的变量res必须使用long类型。函数命名与封装将核心筛法过程封装在getEulers(int n)方法中是一个好习惯使主逻辑清晰也便于调试和复用。5. 模板的变通如何应对不同场景需求上面给出的模板是“计算1到n所有欧拉函数值并求和”的完整解决方案。但在实际做题或面试中问题可能会稍有变化我们需要灵活调整。场景一只需要计算单个数的欧拉函数但需要多次查询。如果题目是给你多个n每次询问φ(n)。这时预处理1到最大范围N的所有φ值每次查询就是O(1)的复杂度。我们的模板完全适用只需在main函数中调用一次getEulers(N)之后直接读取phi[x]即可。这体现了“空间换时间”的思想。场景二只需要判断或使用质数同时需要欧拉函数。我们的模板在筛出质数列表primes的同时也求得了phi。如果你的问题需要同时用到这两个信息这个模板就一举两得了。场景三数据范围极大例如n10^7或更大内存紧张。我们的模板使用了三个O(n)的数组primes,phi,st。当n非常大时这可能占用上百MB内存。此时可以考虑使用BitSet替代boolean[] st来节省空间因为BitSet内部按位存储。但需要注意BitSet的访问和设置比数组稍慢在时间允许的情况下可以考虑。// 使用BitSet的示例 import java.util.BitSet; BitSet st new BitSet(N); ... if (!st.get(i)) { ... } st.set(primes[j] * i);场景四分解质因数模板与筛法模板的选择。这是初学者常问的问题。如何选择使用分解质因数模板本文第2节方法一的情况只需要计算单个或极少数数的欧拉函数。数字n本身非常大但需要计算φ(n)此时无法预处理那么大的范围。面试中面试官明确要求展示质因数分解的能力。使用线性筛模板的情况需要计算一个连续区间内所有数的欧拉函数。需要频繁查询不同n的φ(n)且n的范围在可预处理之内。问题本身就需要用到质数表或线性筛的框架。简单来说“少量单点查询用分解大量区间预处理用筛法”。6. 典型错误分析与调试技巧即便理解了原理和模板亲手实现时还是可能遇到各种问题。下面我列举几个我踩过的坑和调试方法错误1结果输出为0或负数。可能原因1累加和res使用了int类型发生溢出。解决务必使用long。可能原因2phi[]数组没有正确初始化特别是phi[1]。确保getEulers函数中第一行是phi[1] 1。可能原因3循环边界错误。检查getEulers中的for (int i 2; i n; i)和for (int j 0; primes[j] n / i; j)。后者是核心确保j cnt的条件隐含在primes[j] n / i中因为质数数组是递增的当primes[j]太大时条件不满足循环自然结束。错误2运行超时TLE。可能原因没有正确break导致算法退化为O(n^2)的复杂度。仔细检查在if (i % primes[j] 0)分支中计算完phi后是否立即break。检查方法可以写一个简单的测试输入n10^6观察程序运行时间。线性筛应该在毫秒级完成。如果很慢几乎可以肯定是break逻辑有问题。错误3数组越界ArrayIndexOutOfBounds。可能原因1静态数组primes开得太小。线性筛中质数个数大约是n / log(n)对于n10^6质数个数约7.8万。primes数组大小应略大于这个值通常直接开和N一样大是安全的。可能原因2在primes[j] n / i这个条件中当j等于质数数组的实际长度cnt时primes[j]会越界。我们的写法之所以正确是因为当j增长到cnt时primes[j]是0int数组默认值0 n/i这个条件对于正数n/i通常为false除非n/i也为0但这不可能循环终止。这是一种简洁的写法。更安全的写法是加上j cnt的条件for (int j 0; j cnt primes[j] n / i; j)。调试技巧小数据验证不要一上来就用大数据测试。用n10, 20这样的小数据手动计算出每个数的欧拉函数然后打印出程序计算的phi[]数组进行对比。打印中间变量在getEulers循环中打印出i,primes[j],phi[i * primes[j]]的值观察状态转移是否符合我们推导的两种情况。专注边界特别注意i1 i质数以及i%primes[j]0的第一个时刻例如i4, primes[j]2这些边界点的逻辑是否正确。7. 举一反三线性筛框架的其他应用掌握线性筛求欧拉函数真正的价值在于你学会了一个强大的框架。这个框架可以用于计算其他常见的积性函数。所谓积性函数就是对于任意互质的正整数a, b满足f(a*b) f(a) * f(b)的函数。欧拉函数φ(n)就是积性函数。例子1求莫比乌斯函数 μ(n)。莫比乌斯函数的定义是μ(1) 1若n含有平方因子则μ(n)0若n是k个不同质数的乘积则μ(n)(-1)^k在线性筛中我们可以这样维护if (!st[i]) { primes[cnt] i; mu[i] -1; // 单个质数k1 (-1)^1 -1 } for (int j0; primes[j]n/i; j) { st[primes[j]*i] true; if (i % primes[j] 0) { mu[primes[j]*i] 0; // i包含primes[j]的平方因子 break; } else { mu[primes[j]*i] -mu[i]; // 多了一个新的不同质因子符号取反 } }例子2求约数个数函数 d(n)。设n p1^a1 * p2^a2 * ... * pk^ak则d(n) (a11)(a21)...*(ak1)。 我们需要额外维护一个数组minp[]或a[]记录每个数最小质因子的指数。// 假设 num[i] 记录i的约数个数 minp[i]记录i的最小质因子的指数1 if (!st[i]) { primes[cnt] i; num[i] 2; // 质数只有1和自身两个约数 minp[i] 1; // 指数为1所以1后为2 } for (int j0; primes[j]n/i; j) { st[primes[j]*i] true; if (i % primes[j] 0) { minp[primes[j]*i] minp[i] 1; // 最小质因子指数增加1 num[primes[j]*i] num[i] / minp[i] * (minp[i] 1); // 更新约数个数 break; } else { minp[primes[j]*i] 1; // 新的最小质因子指数为1 num[primes[j]*i] num[i] * 2; // 约数个数翻倍乘(11) } }看到这里你会发现模式是高度一致的在i % primes[j] 0的break分支处理最小质因子次数增加的情况在else分支处理新增一个互质质因子的情况。理解了这个模式你就能用线性筛框架解决一大类数论函数前缀和的问题。最后我个人的一点体会是学习算法模板切忌死记硬背。一定要像我们今天这样把背后的数学推导和状态转移关系弄明白。当初我学习时就是亲手把phi[i * primes[j]]的两种情况的公式推导了好几遍直到它变成一种直觉。下次当你需要用到“筛法求欧拉函数”时希望你能直接回忆起“互质就乘(p-1)不互质即整除就乘p”这个核心口诀并能够自己重新推导出完整的代码。这才是真正掌握了这个知识。