1. 项目概述从“亲戚”到数论一个经典问题的深度剖析看到“Relatives”这个标题你可能会联想到人际关系或家庭伦理。但在算法竞赛和数论领域这其实是一个相当经典的题目它考察的核心是欧拉函数的计算。题目通常这样描述给定一个正整数N求小于N且与N互质的正整数的个数。这个“互质”的关系就像数字之间的“亲戚”关系——没有大于1的公共因子彼此“最简”。所以题目“Relatives”的本质就是计算欧拉函数 φ(N) 的值。为什么这个问题如此重要在公钥加密体系如RSA、随机数生成、乃至一些组合数学问题中快速计算一个数的欧拉函数值是基础操作。暴力遍历检查每个数是否与N互质时间复杂度是O(N log N)当N达到10^9甚至更大时完全不可行。这就需要我们搬出数论中的利器素数筛法结合欧拉函数的性质。本文将彻底拆解这个“素数筛欧拉函数”的组合拳不仅告诉你如何做更深入剖析每一步背后的数学原理和工程化实现的精妙之处。无论你是正在备战算法竞赛的选手还是对基础数论感兴趣的程序员这篇从实战中总结的干货都能让你透彻理解并熟练应用。2. 核心思路与数学原理拆解2.1 欧拉函数定义与基础性质欧拉函数 φ(n)定义为小于等于n的正整数中与n互质的数的个数。几个关键性质是我们算法的基石积性函数性质如果两个正整数a和b互质gcd(a, b)1那么 φ(a*b) φ(a) * φ(b)。这是我们将大问题分解为小问题的关键。质数幂次公式若p是一个质数则 φ(p^k) p^k - p^(k-1) p^(k-1) * (p - 1)。这给出了对单个质因数幂次的计算方法。通用计算公式若n的标准分解式为 n p1^k1 * p2^k2 * ... * pm^km其中pi为质数则根据积性有 φ(n) n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pm) 这个公式直观地反映了“剔除非互质数”的过程减去所有是p1倍数的数但这样会重复减去同时是p1和p2倍数的数即p1*p2的倍数……最终用容斥原理导出了这个连乘形式。基于通用公式一个最直接的算法思路就出来了对N进行质因数分解得到所有不同的质因数p然后套用公式计算。这个算法的时间复杂度主要取决于质因数分解的速度。对于单个N试除法分解的复杂度是O(√N)。这在很多情况下已经足够好但当我们遇到需要预处理一段区间内所有数的欧拉函数值时例如求解N个查询或者需要用到区间内所有φ值进行后续计算就需要更高效的批量处理方法。这时“素数筛欧拉函数”的联动就登场了。2.2 素数筛法选型为什么是线性筛素数筛法的目标是以低于逐个判断的方式高效标记出一段区间内的所有质数。常见的筛法有埃拉托斯特尼筛法从2开始将每个质数的倍数标记为合数。时间复杂度约为O(n log log n)。在标记合数的过程中我们其实已经知道了每个数的一个质因数即标记它的那个质数。利用这个信息我们可以在筛的同时递推计算欧拉函数值这就是“欧拉筛”的一种实现。但埃氏筛的一个小缺点是一个合数可能被多个质数重复标记例如6会被2和3都标记这在递推φ值时需要小心处理逻辑。线性筛也称为欧拉筛其核心思想是确保每个合数只被其最小的质因数筛掉一次。这带来了O(n)的线性时间复杂度。正是这个“每个合数只被最小质因数筛一次”的特性使得我们可以在筛的过程中根据当前数与质数的关系以O(1)的代价递推计算出每个数的φ值完美匹配了欧拉函数的积性性质。注意这里的“欧拉筛”指的是线性时间复杂度的素数筛法与我们要求解的“欧拉函数”是两回事只是都冠以欧拉之名。线性筛是实现批量计算欧拉函数最高效的载体。选择线性筛的理由效率最高O(n)的预处理时间复杂度使得后续查询每个数的φ值都是O(1)。逻辑清晰筛法过程与φ值递推过程可以紧密耦合代码简洁优雅。一石二鸟一次预处理同时得到了区间内所有质数列表和所有数的欧拉函数值性价比极高。因此在“Relatives”这类问题需要处理大量数据或区间查询时线性筛是预处理阶段不二的选择。接下来我们就深入线性筛的内部看它如何与欧拉函数的计算完美融合。3. 算法核心线性筛中递推欧拉函数这是整个实现中最精妙的部分。我们目标是得到一个数组phi[]其中phi[i]存储整数 i 的欧拉函数值。同时我们维护一个质数列表primes和一个布尔数组isPrime[]来标记是否质数。3.1 递推的初始状态与边界首先设定边界phi[1] 1。根据定义小于等于1且与1互质的数只有1本身。对于任意质数pphi[p] p - 1。因为1到p-1的所有数都与质数p互质。在线性筛的主循环中我们遍历区间内的每一个整数i从2开始。3.2 递推关系的三种情况假设当前遍历到整数i我们用它来筛掉后续的合数。对于质数列表primes中的每一个质数primes[j]记为p我们标记合数i * p。在标记的同时根据i和p的关系决定如何计算phi[i * p]。这里分三种情况是理解算法的关键情况一i % p 0(即p整除i)这意味着p是i的一个质因数。设i p^k * m其中m与p互质。 那么i * p p^(k1) * m。 根据欧拉函数公式φ(i * p) (i * p) * (1 - 1/p) * (其他与m相关的连乘部分)而φ(i) i * (1 - 1/p) * (其他与m相关的连乘部分)对比两式可以发现φ(i * p) p * φ(i)。直观理解i已经包含了质因数pi*p只是增加了p的指数并未引入新的质因数。根据公式φ(i*p)只是在φ(i)的基础上多乘了一个p因为n变成了n*p而连乘部分(1-1/p)已经存在且不变。情况二i % p ! 0(即p不整除i)这意味着p是i * p的一个新的质因数且i与p互质。 由于欧拉函数是积性函数对于互质的两个数i和p有φ(i * p) φ(i) * φ(p)而φ(p) p - 1。 所以φ(i * p) φ(i) * (p - 1)。情况三当前数i本身是质数在循环开始时如果发现i是质数未被标记则将其加入质数列表primes并直接设置phi[i] i - 1。这是递推的起点。3.3 算法流程与代码骨架结合以上递推关系我们可以写出完整的预处理函数。以下以C为例展示核心代码逻辑并附详细注释。#include vector using namespace std; const int MAX_N 1000000; // 预处理的上限 vectorint primes; // 存储所有筛出的质数 bool isPrime[MAX_N 1]; // 标记数组默认应初始化为true int phi[MAX_N 1]; // 存储欧拉函数值 void linear_sieve_phi(int n) { // 初始化 fill(isPrime, isPrime n 1, true); primes.clear(); phi[1] 1; // 边界条件 for (int i 2; i n; i) { if (isPrime[i]) { primes.push_back(i); phi[i] i - 1; // 情况三i是质数 } // 用当前数i和已知质数筛合数 for (int j 0; j primes.size(); j) { long long nextNum 1LL * i * primes[j]; // 防止溢出 if (nextNum n) break; // 超过范围退出内层循环 isPrime[nextNum] false; // 标记合数 // 关键递推部分 if (i % primes[j] 0) { // 情况一primes[j]是i的质因数 phi[nextNum] phi[i] * primes[j]; break; // 线性筛的精髓保证每个合数只被最小质因数筛一次 } else { // 情况二primes[j]与i互质 phi[nextNum] phi[i] * (primes[j] - 1); } } } }实操心得代码中if (nextNum n) break;和if (i % primes[j] 0) break;这两个break是线性筛效率的保证。前者控制范围后者确保了“每个合数只被最小质因数筛一次”。当i % primes[j] 0时说明primes[j]是i的最小质因数因为我们是按顺序遍历质数列表那么对于i的其他质因数primes[k] (k j)合数i * primes[k]的最小质因数应该是primes[j]而不是primes[k]它会在未来i i / primes[j] * primes[k]时被primes[j]筛掉。此时跳出循环避免了重复标记。4. 针对“Relatives”问题的完整解决方案有了批量计算欧拉函数的能力我们来看如何解决原问题。题目输入通常是一个正整数N输出φ(N)。我们需要根据数据范围选择策略。4.1 策略一单次查询直接质因数分解如果题目是单次查询且N非常大例如达到10^12预处理整个区间不现实。这时应采用试除法质因数分解结合欧拉函数公式。步骤初始化ans N。从p 2开始循环直到p * p N。如果N % p 0说明p是一个质因数。执行ans ans / p * (p - 1)。这等价于ans * (1 - 1/p)但避免了浮点数运算。将N中的所有p因子除尽while (N % p 0) N / p;。循环结束后如果N 1说明剩下的N本身是一个大于√N的质因数。对ans进行同样的操作ans ans / N * (N - 1)。输出ans。代码示例long long phi_single(long long n) { long long ans n; long long temp n; for (long long p 2; p * p temp; p) { if (temp % p 0) { ans ans / p * (p - 1); // 应用公式 while (temp % p 0) temp / p; // 除尽该因子 } } if (temp 1) { // 处理剩余的大质因子 ans ans / temp * (temp - 1); } return ans; }时间复杂度O(√N)在可接受范围内。4.2 策略二多次查询或区间需求线性筛预处理如果题目需要处理多个N多组测试数据或者需要输出1到N所有数的φ值那么预处理是更优解。步骤读取所有查询找到其中最大的N_max。调用linear_sieve_phi(N_max)函数预处理出1到N_max的所有phi值。对于每个查询N直接输出phi[N]。优势预处理复杂度 O(N_max)此后每次查询都是 O(1)。当查询数量很多时平均效率远高于对每个N单独分解。4.3 策略选择与性能对比策略适用场景时间复杂度 (单次)时间复杂度 (Q次查询)空间复杂度试除法分解N极大(10^7)或单次查询O(√N)O(Q * √N_avg)O(1)线性筛预处理多组查询或需要区间结果预处理O(N_max)查询O(1)O(N_max Q)O(N_max)注意事项选择策略时务必注意数据范围。如果题目明确N≤10^6且有10^5组数据那么线性筛预处理是必须的。如果N≤10^12但只有1组数据试除法则更合适。同时注意phi[1] 1这个边界条件在题目中是否有特殊定义极少数题目可能认为1没有“小于1的正整数”而定义φ(1)0但标准定义是1。5. 实战演练、调试与边界处理理论懂了代码写了但在实际解题尤其是线上判题系统中还有很多细节坑等着我们。5.1 典型输入输出处理“Relatives”类题目的输入输出通常很简单但要注意输入可能包含多个测试用例直到输入0为止。N的范围可能从1开始。输出通常就是φ(N)的值。一个健壮的输入输出框架如下#include iostream using namespace std; const int MAXN 1000000; int phi[MAXN 5]; void init() { // ... 线性筛预处理phi数组的代码 } int main() { init(); // 在程序开始前一次性预处理 int n; while (cin n n ! 0) { // 循环读取直到输入0 cout phi[n] endl; } return 0; }5.2 常见“坑点”与调试技巧整数溢出在计算i * primes[j]时即使i和primes[j]都在int范围内它们的乘积也可能超出int范围导致溢出成为负数进而使得数组访问越界或循环判断出错。务必使用long long类型进行中间计算如long long nextNum 1LL * i * primes[j];。数组越界确保定义的数组大小如phi[MAX_N1]至少比最大N大1因为我们的下标是从1开始使用的。如果题目说N≤1000000那么数组大小至少为1000001。初始化问题isPrime数组需要初始化为true可以用fill或memset注意memset按字节赋值true的非零值可能被赋为0x01在bool判断中通常没问题但更推荐fill。phi[1] 1必须在循环开始前设定好。质数列表primes要记得clear()。算法逻辑错误最常见的是递推公式用错。牢记if (i % p 0) phi[i*p] phi[i] * p;else phi[i*p] phi[i] * (p - 1);可以自己用几个小例子验证比如计算φ(4)、φ(6)、φ(8)。多组数据预处理如果题目没有明确说所有测试用例的N不超过某个值但时间限制宽松可以保守地预处理一个较大的范围如1e6。如果内存紧张再考虑用单次分解法。5.3 性能优化小技巧用数组代替vector在性能要求极高的竞赛中有时用静态数组模拟质数列表比vector稍快因为减少了动态扩容的开销。可以预先估计质数个数约 n/ln(n)。位筛法用bitset存储isPrime信息可以将空间压缩到原来的1/8对于超大范围如1e8的预处理非常有用但访问速度可能稍慢。分块筛当需要计算极大范围如1e12的欧拉函数时内存无法容纳整个phi数组。这时可以使用“分段筛”或“Meissel-Lehmer算法”等更高级的技巧但这已超出本文基础范围。6. 从“Relatives”到更广阔的应用掌握了线性筛求欧拉函数你解锁的不仅仅是一道题。它是许多数论和组合问题的基石。6.1 相关变种与扩展问题区间欧拉函数和求 ∑φ(i) for i in [L, R]。预处理前缀和即可。最大公约数之和求 ∑∑gcd(i, j)。可以通过欧拉函数转化为 ∑ (φ(d) * floor(n/d)^2) 来求解复杂度大幅降低。既约分数计数给定N求有多少个分数a/b满足0ab≤N且a/b是最简分数。这等价于求 ∑φ(i) for i2 to N。模n下的乘法逆元在数论中若a与n互质则a在模n下的逆元存在且为 a^(φ(n)-1) mod n根据欧拉定理。快速计算φ(n)是其中的一步。6.2 算法思想的迁移线性筛的精髓——“用最小质因数标记合数”——可以推广到计算其他积性数论函数。例如莫比乌斯函数 μ(n)同样可以在线性筛中递推。约数个数函数 d(n)和约数和函数 σ(n)只要找到它们关于质数幂次的表达式和积性性质就能在线性筛中一并求出。一个通用的线性筛框架可以同时求出质数、欧拉函数、莫比乌斯函数、最小质因数等代码结构高度相似只是递推公式不同。这体现了算法设计的模块化和复用思想。最后回顾整个“Relatives”问题的解决过程从理解题意到选择策略从推导数学公式到实现精妙递推再到调试优化和思考扩展这正是一个典型算法问题从分析到解决的完整路径。我个人的体会是数论问题往往代码不长但对思维严密性要求极高。理解每一个等号为什么成立每一个if条件背后的数学含义比死记硬背模板重要得多。下次当你遇到需要计算互质个数的问题时希望你能立刻想起“素数筛欧拉函数”这个黄金组合并自信地写出高效的代码。