1. 项目概述当线性筛遇上欧拉函数在算法竞赛和数论问题的求解中欧拉函数Euler‘s Totient Function是一个绕不开的核心概念。它计算的是小于等于 n 的正整数中与 n 互质的数的个数。直接根据定义计算单个欧拉函数的时间复杂度是 O(√n)这在面对需要批量计算比如计算 1 到 N 所有数的欧拉函数时O(N√N) 的复杂度就完全不可接受了。这时筛法的思想就闪亮登场了。标题中的“筛法求欧拉函数”尤其是结合“线性筛”和“模板题”这两个关键词直指一个经典且高效的解决方案在线性筛素数的过程中同步递推求出所有数的欧拉函数值时间复杂度可以优化到 O(N)。这不仅是数论知识点的结合更是对算法“时空权衡”与“过程复用”思想的绝佳实践。对于正在学习数论和算法优化的 C 开发者而言掌握这个方法就相当于获得了一把解决一大类数论相关问题的利器。2. 核心原理深度拆解线性筛与欧拉函数的化学反应要理解这个模板我们必须先拆解它的两个核心组件线性筛欧拉筛和欧拉函数的递推性质并看它们是如何完美融合的。2.1 线性筛欧拉筛的精髓普通的埃氏筛Sieve of Eratosthenes在标记合数时会有重复例如 12 会被 2 和 3 各标记一次。线性筛通过一个关键规则确保了每个合数只被其最小质因子筛掉一次从而达到 O(N) 的线性时间复杂度。其核心流程与数据结构如下维护一个布尔数组is_prime[]或st[]记录每个数是否是质数初始化为 true。维护一个数组primes[]动态存储已发现的质数。外层循环i从 2 遍历到 N。如果i是质数is_prime[i] true则将其加入primes数组。内层循环遍历当前已得到的质数列表primes[j]。计算composite i * primes[j]。这个数composite的最小质因子一定是primes[j]。标记is_prime[composite] false。关键终止条件当i % primes[j] 0时跳出内层循环。因为此时primes[j]已是i的最小质因子对于下一个更大的质数primes[j1]i * primes[j1]的最小质因子应该是primes[j]而不是primes[j1]如果继续标记会导致重复。这个条件是线性复杂度的保证。注意线性筛的内层循环条件通常有两个j primes.size()和i * primes[j] N。后者是为了防止数组越界是必须的边界检查。2.2 欧拉函数的定义与递推公式欧拉函数 φ(n) 的计算基于整数的质因数分解。若 n 有标准分解式 n p1^k1 * p2^k2 * ... * pm^km其中 pi 是质数则 φ(n) n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pm)从这个公式可以推导出几个关键的递推性质正是我们能在筛法中使用的质数 pφ(p) p - 1。所有小于 p 的正整数都与 p 互质。p 是质数且 p 能整除 n设 n p^k * m其中 m 与 p 互质。则有 φ(n) φ(p^k * m) p^(k-1) * (p-1) * φ(m)。更常用的是它的一个特例当 n 是质数 p 的倍数时即i % p 0φ(i * p) p * φ(i)。p 是质数且 p 不能整除 n根据积性函数性质当两数互质时φ(n * p) φ(n) * φ(p) φ(n) * (p - 1)。性质2和3为我们提供了根据已知 φ(i) 计算 φ(i * p) 的路径而线性筛的过程恰好就是在生成i * primes[j]这样的数对2.3 融合策略在线性筛的每个步骤中决定如何递推在线性筛的主循环中当我们用质数p即primes[j]去标记合数x i * p时我们同时知道了i和p的关系。这正是计算 φ(x) 的绝佳时机情况一i % p 0。这意味着p是i的质因子。根据上述性质2φ(x) p * φ(i)。情况二i % p ! 0。这意味着p与i互质。根据上述性质3φ(x) φ(i) * (p - 1)。因此我们只需要在开始筛法前初始化一个数组phi[]其中phi[1] 1定义。然后在筛法的循环体中在标记合数的同时按照上述两条规则同步更新phi[x]即可。由于线性筛保证了每个合数只被其最小质因子访问一次所以每个phi[x]也只会被计算一次整个过程依然是 O(N) 的。3. 代码实现与逐行解析理解了原理我们来看 C 的模板实现。这里会提供一个清晰、健壮且带有详细注释的版本。#include iostream #include vector using namespace std; const int N 1000010; // 根据题目数据范围定义例如1e6 int primes[N], cnt; // primes[]存储所有素数cnt是计数 int phi[N]; // 存储每个数的欧拉函数值 bool st[N]; // st[x]存储x是否被筛掉非素数 long long 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 } // 遍历已知素数筛选合数 for (int j 0; primes[j] n / i; j) { // 防溢出条件primes[j] * i n 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); } } } // 计算1到n所有欧拉函数值的和根据题目要求本题是求和 long long 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;这是欧拉函数的定义必须初始化。if (!st[i])判断i是否为素数。初始时所有数都未被标记第一个遇到的i2自然是素数。phi[i] i - 1;对应原理中的性质1素数的欧拉函数值。for (int j 0; primes[j] n / i; j)这是内层循环。条件primes[j] n / i等价于primes[j] * i n是防止后续计算溢出的关键务必牢记。写成乘法判断可能会因溢出导致死循环或数组越界。st[primes[j] * i] true;线性筛的标准操作标记合数。if (i % primes[j] 0) {... break;}phi[primes[j] * i] phi[i] * primes[j];对应情况一的递推公式。break;是线性筛算法的灵魂。它保证了每个合数只被其最小质因子筛一次。当primes[j]能整除i时primes[j]就是i的最小质因子因为primes[]是递增的那么对于当前i和更大的primes[j1]合数i * primes[j1]的最小质因子应该是primes[j]而不是primes[j1]。如果继续循环这个数会在后面被primes[j]再次筛到造成重复。因此必须跳出。else {...}对应情况二phi[primes[j] * i] phi[i] * (primes[j] - 1);。最后的累加循环for (int i 1; i n; i) res phi[i];是题目AcWing 874的要求计算从 1 到 n 所有欧拉函数值的和。如果题目要求的是单个值或数组可以灵活调整输出部分。4. 模板的变通与应用场景这个模板之所以称为“模板题”是因为其核心逻辑固定但可以根据不同需求进行微调。4.1 常见变体与调整仅求欧拉函数数组如果题目只需要phi[]数组而不需要求和直接移除最后的累加步骤在get_eulers函数结束后phi[1...n]就已经是正确结果了。求单个大数的欧拉函数对于单个大数 n (n 1e12 或更大)无法用筛法需要使用基于质因数分解的公式法。模板不适用。结合其他积性函数线性筛的强大之处在于可以同时求多个积性函数例如约数个数、约数和等。思路类似都需要根据i % primes[j]是否等于 0 来设计递推公式。例如求莫比乌斯函数 μ(n) 也可以在线性筛中完成。数据范围与数组类型N的大小需要根据题目上限设定。phi[]和结果res的类型要注意当 n 较大时欧拉函数之和可能超出int范围需使用long long。4.2 典型应用场景数论题目预处理许多数论题需要频繁查询多个数的欧拉函数值。在程序开始时用 O(N) 的时间预处理出phi数组之后就可以 O(1) 查询这是典型的“空间换时间”。欧拉定理与模幂运算欧拉定理指出若 a 与 n 互质则 a^φ(n) ≡ 1 (mod n)。这在计算大指数模运算如 RSA 解密时至关重要。预处理 φ(n) 可以加速计算。原根判定在有限循环群中原根的个数是 φ(φ(n))。寻找原根时需要先计算 φ(n)。莫比乌斯反演等高级数论技巧的前置步骤这些技巧常常需要用到欧拉函数的前缀和。5. 实战调试与性能优化心得在实际编码和竞赛中围绕这个模板有几个容易出错和可以优化的点。5.1 常见错误排查表错误现象可能原因解决方案输出结果错误比预期小很多1.phi[1]未初始化为 1。2. 内层循环条件写成了primes[j] * i n导致整数溢出j失控。3. 递推公式用错混淆了情况一和情况二。1. 检查初始化。2.务必将条件改为primes[j] n / i。3. 牢记i % p 0时乘p否则乘p-1。程序运行超时 (TLE)1. 使用了埃氏筛而非线性筛复杂度为 O(N log log N)对于 N1e6 尚可N1e7 可能卡常数。2. 数组访问频繁缓存不友好相对次要。1. 确认代码中是否有break语句这是线性筛的标志。2. 确保使用vectorbool或原生数组vectorint标记会慢一些。内存超限 (MLE)数组N开得过大超过了题目内存限制。精确估算内存三个int数组primes,phi,st约占用 3 * N * 4 字节。N1e7 时约 114MB。需根据题目限制调整。结果部分正确求和变量res的数据类型是int发生溢出。将res的类型改为long long。5.2 性能优化与技巧使用vectorbool优化空间bool st[N]在内存中不一定只占1比特。使用std::vectorbool st(N, false)是 C STL 的一种特化它通常以位图方式存储可以节省约 7/8 的内存。对于 N 非常大的情况如 1e8这个优化至关重要。vectorbool st(N, false); // 访问时和数组一样if (!st[i]) ...循环条件的写法primes[j] n / i是防溢出的标准写法。写成primes[j] * i n在i和primes[j]都很大时乘法结果可能超出int范围导致溢出为负数条件判断错误从而引起数组越界或死循环。这是一个非常隐蔽的 bug。函数封装与全局变量将筛法过程封装在get_eulers()函数内primes,phi,st等数组作为全局变量或静态变量可以避免在函数间传递大数组的开销。这也是竞赛中的常见做法。输入输出加速当n很大如 1e7且需要多次调用或有多组数据时关闭 C 标准流同步或使用 C 标准 IO 可以显著提升速度。ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);6. 从模板到理解为何线性筛是“过程复用”的典范很多初学者会问先筛出素数再根据素数去单独计算每个数的欧拉函数不行吗当然可以但那样效率更低。线性筛求欧拉函数模板的精妙之处在于它实现了“过程复用”。筛法本身就是一个遍历所有数、分析其质因子构成的过程。而欧拉函数的计算核心也依赖于数的质因子构成。这两个过程在数学本质上高度重合。线性筛在完成其核心任务标记合数、收集质数的每一个关键步骤i * primes[j]中恰好提供了计算欧拉函数所需的所有信息i的欧拉值以及i与primes[j]是否互质。因此我们几乎不增加额外的计算量仅多了几次乘法和赋值就“顺带”完成了另一个复杂函数的批量计算。这种思想在算法设计中非常宝贵。它提醒我们在解决复杂问题时不要孤立地看待每一个子任务。仔细分析任务之间的内在联系寻找可以共享的中间结果或计算过程往往能催生出时间复杂度与空间复杂度俱佳的优秀算法。这个模板不仅仅是一个需要记忆的代码片段更是这种“高效整合”思维模式的体现。当你下次遇到需要同时预处理多个积性函数如约数个数、莫比乌斯函数的问题时你会立刻想到“也许我可以在一个线性筛里把它们全都搞定。” 线性筛法高效求解欧拉函数：原理、C++实现与模板解析
1. 项目概述当线性筛遇上欧拉函数在算法竞赛和数论问题的求解中欧拉函数Euler‘s Totient Function是一个绕不开的核心概念。它计算的是小于等于 n 的正整数中与 n 互质的数的个数。直接根据定义计算单个欧拉函数的时间复杂度是 O(√n)这在面对需要批量计算比如计算 1 到 N 所有数的欧拉函数时O(N√N) 的复杂度就完全不可接受了。这时筛法的思想就闪亮登场了。标题中的“筛法求欧拉函数”尤其是结合“线性筛”和“模板题”这两个关键词直指一个经典且高效的解决方案在线性筛素数的过程中同步递推求出所有数的欧拉函数值时间复杂度可以优化到 O(N)。这不仅是数论知识点的结合更是对算法“时空权衡”与“过程复用”思想的绝佳实践。对于正在学习数论和算法优化的 C 开发者而言掌握这个方法就相当于获得了一把解决一大类数论相关问题的利器。2. 核心原理深度拆解线性筛与欧拉函数的化学反应要理解这个模板我们必须先拆解它的两个核心组件线性筛欧拉筛和欧拉函数的递推性质并看它们是如何完美融合的。2.1 线性筛欧拉筛的精髓普通的埃氏筛Sieve of Eratosthenes在标记合数时会有重复例如 12 会被 2 和 3 各标记一次。线性筛通过一个关键规则确保了每个合数只被其最小质因子筛掉一次从而达到 O(N) 的线性时间复杂度。其核心流程与数据结构如下维护一个布尔数组is_prime[]或st[]记录每个数是否是质数初始化为 true。维护一个数组primes[]动态存储已发现的质数。外层循环i从 2 遍历到 N。如果i是质数is_prime[i] true则将其加入primes数组。内层循环遍历当前已得到的质数列表primes[j]。计算composite i * primes[j]。这个数composite的最小质因子一定是primes[j]。标记is_prime[composite] false。关键终止条件当i % primes[j] 0时跳出内层循环。因为此时primes[j]已是i的最小质因子对于下一个更大的质数primes[j1]i * primes[j1]的最小质因子应该是primes[j]而不是primes[j1]如果继续标记会导致重复。这个条件是线性复杂度的保证。注意线性筛的内层循环条件通常有两个j primes.size()和i * primes[j] N。后者是为了防止数组越界是必须的边界检查。2.2 欧拉函数的定义与递推公式欧拉函数 φ(n) 的计算基于整数的质因数分解。若 n 有标准分解式 n p1^k1 * p2^k2 * ... * pm^km其中 pi 是质数则 φ(n) n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pm)从这个公式可以推导出几个关键的递推性质正是我们能在筛法中使用的质数 pφ(p) p - 1。所有小于 p 的正整数都与 p 互质。p 是质数且 p 能整除 n设 n p^k * m其中 m 与 p 互质。则有 φ(n) φ(p^k * m) p^(k-1) * (p-1) * φ(m)。更常用的是它的一个特例当 n 是质数 p 的倍数时即i % p 0φ(i * p) p * φ(i)。p 是质数且 p 不能整除 n根据积性函数性质当两数互质时φ(n * p) φ(n) * φ(p) φ(n) * (p - 1)。性质2和3为我们提供了根据已知 φ(i) 计算 φ(i * p) 的路径而线性筛的过程恰好就是在生成i * primes[j]这样的数对2.3 融合策略在线性筛的每个步骤中决定如何递推在线性筛的主循环中当我们用质数p即primes[j]去标记合数x i * p时我们同时知道了i和p的关系。这正是计算 φ(x) 的绝佳时机情况一i % p 0。这意味着p是i的质因子。根据上述性质2φ(x) p * φ(i)。情况二i % p ! 0。这意味着p与i互质。根据上述性质3φ(x) φ(i) * (p - 1)。因此我们只需要在开始筛法前初始化一个数组phi[]其中phi[1] 1定义。然后在筛法的循环体中在标记合数的同时按照上述两条规则同步更新phi[x]即可。由于线性筛保证了每个合数只被其最小质因子访问一次所以每个phi[x]也只会被计算一次整个过程依然是 O(N) 的。3. 代码实现与逐行解析理解了原理我们来看 C 的模板实现。这里会提供一个清晰、健壮且带有详细注释的版本。#include iostream #include vector using namespace std; const int N 1000010; // 根据题目数据范围定义例如1e6 int primes[N], cnt; // primes[]存储所有素数cnt是计数 int phi[N]; // 存储每个数的欧拉函数值 bool st[N]; // st[x]存储x是否被筛掉非素数 long long 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 } // 遍历已知素数筛选合数 for (int j 0; primes[j] n / i; j) { // 防溢出条件primes[j] * i n 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); } } } // 计算1到n所有欧拉函数值的和根据题目要求本题是求和 long long 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;这是欧拉函数的定义必须初始化。if (!st[i])判断i是否为素数。初始时所有数都未被标记第一个遇到的i2自然是素数。phi[i] i - 1;对应原理中的性质1素数的欧拉函数值。for (int j 0; primes[j] n / i; j)这是内层循环。条件primes[j] n / i等价于primes[j] * i n是防止后续计算溢出的关键务必牢记。写成乘法判断可能会因溢出导致死循环或数组越界。st[primes[j] * i] true;线性筛的标准操作标记合数。if (i % primes[j] 0) {... break;}phi[primes[j] * i] phi[i] * primes[j];对应情况一的递推公式。break;是线性筛算法的灵魂。它保证了每个合数只被其最小质因子筛一次。当primes[j]能整除i时primes[j]就是i的最小质因子因为primes[]是递增的那么对于当前i和更大的primes[j1]合数i * primes[j1]的最小质因子应该是primes[j]而不是primes[j1]。如果继续循环这个数会在后面被primes[j]再次筛到造成重复。因此必须跳出。else {...}对应情况二phi[primes[j] * i] phi[i] * (primes[j] - 1);。最后的累加循环for (int i 1; i n; i) res phi[i];是题目AcWing 874的要求计算从 1 到 n 所有欧拉函数值的和。如果题目要求的是单个值或数组可以灵活调整输出部分。4. 模板的变通与应用场景这个模板之所以称为“模板题”是因为其核心逻辑固定但可以根据不同需求进行微调。4.1 常见变体与调整仅求欧拉函数数组如果题目只需要phi[]数组而不需要求和直接移除最后的累加步骤在get_eulers函数结束后phi[1...n]就已经是正确结果了。求单个大数的欧拉函数对于单个大数 n (n 1e12 或更大)无法用筛法需要使用基于质因数分解的公式法。模板不适用。结合其他积性函数线性筛的强大之处在于可以同时求多个积性函数例如约数个数、约数和等。思路类似都需要根据i % primes[j]是否等于 0 来设计递推公式。例如求莫比乌斯函数 μ(n) 也可以在线性筛中完成。数据范围与数组类型N的大小需要根据题目上限设定。phi[]和结果res的类型要注意当 n 较大时欧拉函数之和可能超出int范围需使用long long。4.2 典型应用场景数论题目预处理许多数论题需要频繁查询多个数的欧拉函数值。在程序开始时用 O(N) 的时间预处理出phi数组之后就可以 O(1) 查询这是典型的“空间换时间”。欧拉定理与模幂运算欧拉定理指出若 a 与 n 互质则 a^φ(n) ≡ 1 (mod n)。这在计算大指数模运算如 RSA 解密时至关重要。预处理 φ(n) 可以加速计算。原根判定在有限循环群中原根的个数是 φ(φ(n))。寻找原根时需要先计算 φ(n)。莫比乌斯反演等高级数论技巧的前置步骤这些技巧常常需要用到欧拉函数的前缀和。5. 实战调试与性能优化心得在实际编码和竞赛中围绕这个模板有几个容易出错和可以优化的点。5.1 常见错误排查表错误现象可能原因解决方案输出结果错误比预期小很多1.phi[1]未初始化为 1。2. 内层循环条件写成了primes[j] * i n导致整数溢出j失控。3. 递推公式用错混淆了情况一和情况二。1. 检查初始化。2.务必将条件改为primes[j] n / i。3. 牢记i % p 0时乘p否则乘p-1。程序运行超时 (TLE)1. 使用了埃氏筛而非线性筛复杂度为 O(N log log N)对于 N1e6 尚可N1e7 可能卡常数。2. 数组访问频繁缓存不友好相对次要。1. 确认代码中是否有break语句这是线性筛的标志。2. 确保使用vectorbool或原生数组vectorint标记会慢一些。内存超限 (MLE)数组N开得过大超过了题目内存限制。精确估算内存三个int数组primes,phi,st约占用 3 * N * 4 字节。N1e7 时约 114MB。需根据题目限制调整。结果部分正确求和变量res的数据类型是int发生溢出。将res的类型改为long long。5.2 性能优化与技巧使用vectorbool优化空间bool st[N]在内存中不一定只占1比特。使用std::vectorbool st(N, false)是 C STL 的一种特化它通常以位图方式存储可以节省约 7/8 的内存。对于 N 非常大的情况如 1e8这个优化至关重要。vectorbool st(N, false); // 访问时和数组一样if (!st[i]) ...循环条件的写法primes[j] n / i是防溢出的标准写法。写成primes[j] * i n在i和primes[j]都很大时乘法结果可能超出int范围导致溢出为负数条件判断错误从而引起数组越界或死循环。这是一个非常隐蔽的 bug。函数封装与全局变量将筛法过程封装在get_eulers()函数内primes,phi,st等数组作为全局变量或静态变量可以避免在函数间传递大数组的开销。这也是竞赛中的常见做法。输入输出加速当n很大如 1e7且需要多次调用或有多组数据时关闭 C 标准流同步或使用 C 标准 IO 可以显著提升速度。ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);6. 从模板到理解为何线性筛是“过程复用”的典范很多初学者会问先筛出素数再根据素数去单独计算每个数的欧拉函数不行吗当然可以但那样效率更低。线性筛求欧拉函数模板的精妙之处在于它实现了“过程复用”。筛法本身就是一个遍历所有数、分析其质因子构成的过程。而欧拉函数的计算核心也依赖于数的质因子构成。这两个过程在数学本质上高度重合。线性筛在完成其核心任务标记合数、收集质数的每一个关键步骤i * primes[j]中恰好提供了计算欧拉函数所需的所有信息i的欧拉值以及i与primes[j]是否互质。因此我们几乎不增加额外的计算量仅多了几次乘法和赋值就“顺带”完成了另一个复杂函数的批量计算。这种思想在算法设计中非常宝贵。它提醒我们在解决复杂问题时不要孤立地看待每一个子任务。仔细分析任务之间的内在联系寻找可以共享的中间结果或计算过程往往能催生出时间复杂度与空间复杂度俱佳的优秀算法。这个模板不仅仅是一个需要记忆的代码片段更是这种“高效整合”思维模式的体现。当你下次遇到需要同时预处理多个积性函数如约数个数、莫比乌斯函数的问题时你会立刻想到“也许我可以在一个线性筛里把它们全都搞定。”