我印象很深第一次在算法题里被欧拉函数卡住是那道“求 1 到 n 里所有与 n 互质的数的个数”。题目看起来很短数据范围一上来就是 10^9暴力枚举想都不用想。后来认真把欧拉函数的定义、证明、推导完整过了一遍才发现这类题的套路非常固定先判断是不是在问互质个数再决定用哪种求法。这篇文章不灌水从定义讲起把 phi(p^k)、积性函数、通式三条核心性质的证明一步步写清楚然后给出试除法、埃氏筛、线性筛三种代码实现最后把我在刷题里踩过的坑和常用变形整理成速查表。适合正在准备算法竞赛、面试手撕算法或者单纯想把数论基础补扎实的读者。“每日一遍算法再见”这句话很多人当玩笑但如果你真的把欧拉函数这种基础数论每天推一遍效果确实很明显。1. 欧拉函数到底在算什么1.1 定义与一个朴素例子欧拉函数记作 φ(n)读作 phi(n)它表示从 1 到 n 这 n 个整数里有多少个整数和 n 的最大公约数是 1也就是和 n 互质的个数。特别规定 φ(1) 1。为什么这样规定因为后面筛法和递推公式都要从 φ(1) 起步不给个值整个体系会断掉。直接看例子最直观。φ(6)1 到 6 里和 6 互质的是 1 和 5其他 2、3、4、6 都和 6 有公共因子所以 φ(6) 2。φ(10)1、3、7、9 四个数和 10 互质所以 φ(10) 4。不要小看这个“数个数”的过程很多算法题的题意绕了几层之后本质上就是在问一个 φ。为了后面写筛法时能验算我先把 1 到 12 的欧拉函数值列一张表n123456789101112φ(n)1122426464104注意 φ(9) 6因为 1 到 9 里和 9 互质的是 1、2、4、5、7、8正好 6 个。这张表是很好的对照工具以后写代码出错了可以先拿它验证一下。1.2 为什么算法题里处处有它欧拉函数在数论题里的地位相当于排序在数据结构里的地位属于“你逃不掉”的基础工具。我总结了一下最常见的出现方式有这么几类。第一类是直接问互质个数。比如“求 1 到 n 中所有与 n 互质的数的个数”这就是 φ(n) 的定义没有任何包装。这种题通常数据范围很大暴力枚举不行必须用公式或筛法预处理。第二类是问“满足 gcd(x, n) d 的 x 有多少个”。这类题看着和互质没关系但稍微转化一下令 x d * y同时 n d * m那么 gcd(x, n) d 等价于 gcd(y, m) 1。所以符合条件的 x 的数量就是 φ(n / d)前提是 d 必须整除 n。这个变形在竞赛里非常高频基本上一看到“最大公约数等于某个值”的计数题就要往 φ 上想。第三类是分数和约分问题。比如统计分母为 n 的最简真分数个数本质就是 φ(n)。再往深了走Farey 序列的长度计算、有理数排序、连分数相关题目都会用到 1 到 n 的 φ 值之和。第四类是模运算相关的题。欧拉定理 a^φ(n) ≡ 1 (mod n) 是快速幂求逆元、大指数降幂的理论基础。很多题表面在考快速幂实际上卡你的就是欧拉函数算不对。第五类是密码学背景最典型的是 RSA。RSA 里取两个大质数 p、q计算 n p * q然后用到 φ(n) (p - 1)(q - 1)。这个公式就是欧拉函数通式的直接推论等你看完第三节的推导会发现它简直是白送。2. 三条核心性质的完整证明2.1 质数幂 phi(p^k) 的证明先证最简单的一条如果 p 是质数那么 φ(p^k) p^k - p^(k-1)。思路是把“互质的个数”转换成“总数减去不互质的个数”。从 1 到 p^k 一共有 p^k 个数。这个区间里的数哪些和 p^k 不互质和 p^k 不互质说明有公共质因子而 p^k 只有一个质因子 p所以只要这个数含有因子 p它就和 p^k 不互质。那么 1 到 p^k 里有多少个数是 p 的倍数它们是 p, 2p, 3p, ..., p^(k-1) * p一共 p^(k-1) 个。这里要注意最后一个正好是 p^k 本身它和 p^k 当然不互质所以也包含在这 p^(k-1) 个里面。总数 p^k 减去这 p^(k-1) 个就得到 φ(p^k) p^k - p^(k-1)。你也可以把它写成 p^k * (1 - 1/p)这个写法在后面通式推导里会反复出现。举个例子验证p 2, k 3那么 p^k 8。按公式 φ(8) 8 - 4 4。手动数一下1 到 8 里和 8 互质的是 1、3、5、7正好 4 个对上了。2.2 积性函数的构造性证明第二条性质是整个欧拉函数的核心也是最容易让人半懂不懂的地方当 gcd(m, n) 1 时φ(mn) φ(m) * φ(n)。数学上叫积性函数。注意条件是 m 和 n 互质。很多人记公式时把条件忘了直接在 φ(4) * φ(2) 和 φ(8) 之间画等号那当然不对因为 4 和 2 不互质。为什么必须互质证明过程看得清清楚楚。先声明一个引理因为 gcd(m, n) 1所以 m 和 n 没有公共质因子。对于任意整数 agcd(a, mn) 的质因子集合等于 gcd(a, m) 的质因子集合和 gcd(a, n) 的质因子集合的并集而且这两个集合互不相交。因此 gcd(a, mn) 1当且仅当 gcd(a, m) 1 且 gcd(a, n) 1。接下来要引入一个用来“数数”的工具中国剩余定理的最简单版本。因为 gcd(m, n) 1所以 0 到 mn-1 中的每个整数 a和二元组 (a mod m, a mod n) 是一一对应的。换句话说任意给定一个模 m 的余数 x 和一个模 n 的余数 y在 0 到 mn-1 里一定能找到一个唯一的 a同时满足 a mod m x、a mod n y。为什么说有这个对应关系直观理解m 和 n 互质时它们的“周期”不会错位一定能拼出一个唯一的数。拿 m 3, n 4 举例0 到 11 这 12 个数按 (mod 3, mod 4) 排列a01234567891011(a mod 3, a mod 4)(0,0)(1,1)(2,2)(0,3)(1,0)(2,1)(0,2)(1,3)(2,0)(0,1)(1,2)(2,3)12 个二元组全部出现一个不重一个不漏。现在回到 φ(mn)。从 0 到 mn-1 这 mn 个数里和 mn 互质的数有多少个根据前面的引理这样的 a 必须同时满足 a mod m 与 m 互质且 a mod n 与 n 互质。而二元组一一对应的性质保证了a mod m 可以独立选择 φ(m) 个值a mod n 可以独立选择 φ(n) 个值两者组合起来正好有 φ(m) * φ(n) 种可能。另一方面和 mn 互质的 a 的个数按定义就是 φ(mn)。所以 φ(mn) φ(m) * φ(n)证完。这条性质是整个欧拉函数公式的“乘法基石”。没有它我们没法从质因子单独算再拼出任意 n 的结果。注意积性成立的前提是 gcd(m, n) 1。使用这条性质前务必检查互质条件这是新手最容易翻车的地方。2.3 通式 phi(n) n 乘以连乘积的导出有了 phi(p^k) 和积性欧拉函数的通式就是水到渠成。把 n 做质因数分解写成 n p1^a1 * p2^a2 * ... * pr^ar其中 p1 到 pr 是互不相同的质数。因为 p1^a1、p2^a2、...、pr^ar 这些数两两互质所以可以反复套用积性性质φ(n) φ(p1^a1 * p2^a2 * ... * pr^ar) φ(p1^a1) * φ(p2^a2) * ... * φ(pr^ar)再把 2.1 的结论代入φ(pi^ai) pi^ai - pi^(ai-1) pi^ai * (1 - 1/pi)于是φ(n) p1^a1(1 - 1/p1) * p2^a2(1 - 1/p2) * ... * pr^ar(1 - 1/pr) n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pr)这就是欧拉函数的著名通式。举一个实际例子n 100 2^2 * 5^2那么 φ(100) 100 * (1 - 1/2) * (1 - 1/5) 100 * 1/2 * 4/5 40。除了从积性出发还有一个更直接的证明方法用容斥原理。设 n 的不同质因子为 p1, p2, ..., pr。从 1 到 n 中筛掉所有能被 p1 整除的数再筛掉能被 p2 整除的但这样会把同时能被 p1 和 p2 整除的数重复筛掉所以要加回来。这就是容斥原理的标准流程φ(n) n - Σ n/pi Σ n/(pipj) - Σ n/(pipj*pk) ...右边提取公因子 nφ(n) n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pr)因为右侧连乘展开后正好就是上面那一串容斥式子。两种方法殊途同归一个从积性分解走一个从筛法计数走最后得到同一个公式。我建议两个都要看懂因为面试的时候面试官可能会让你用其中一种现场推导。2.4 一个免费的验算工具约数和恒等式再讲一个经常被忽略但是写代码时特别有用的恒等式对于任意正整数 n所有约数的欧拉函数值加起来等于 n。公式写作 Σ φ(d) n其中 d 遍历 n 的所有正约数。证明也很巧妙。考察所有分母为 n 的分数 m/n其中 m 从 1 取到 n。每个分数约分之后分母一定是 n 的某个约数 d而且分子分母互质。反过来看固定一个约数 d如果约分后分母恰好是 d那么这个分数一定可以写成 a/d其中 1 ≤ a ≤ d 且 gcd(a, d) 1。满足条件的 a 有多少个正好 φ(d) 个。于是m 从 1 到 n 的 n 个分数按照“约分后的分母”分组每一组的大小就是 φ(d)加起来当然等于总分数个数 n。所以 Σ φ(d) n。这个恒等式的实战价值在于验算。你写完筛法随便挑一个 n把它所有约数的 φ 值加起来如果结果不是 n说明代码肯定有 bug。我在对拍时经常用这个性质做快速检查比人肉枚举快得多。3. 从数学到代码三种求法一次讲透3.1 单点查询试除法分解质因数如果题目只问一个 φ(n)最高效的做法是按通式直接分解 n 的质因数边分解边乘系数。代码很短int euler_phi(int n) { int res n; for (int i 2; (long long)i * i n; i) { if (n % i 0) { res res / i * (i - 1); // 相当于乘上 (1 - 1/i) while (n % i 0) n / i; // 把这个质因子除干净 } } if (n 1) res res / n * (n - 1); return res; }这里有几个地方必须解释清楚。为什么循环里找到因子后用res res / i * (i - 1)而不是res * (i - 1) / i因为(i - 1) / i在整数除法里直接变成 0 了。为什么还要先除后乘因为 res 在数学上一定是当前剩余部分对应的 n 的倍数可以整除所以先除后乘既不会丢精度也能避免res * (i - 1)中间结果溢出。为什么找到一个因子后要用 while 循环把它除干净因为通式里每个不同质因子只乘一次。如果 n 12 2^2 * 3循环到 i 2 时要把 12 里的两个 2 都去掉变成 3这样后面 i 3 才能正确处理否则到 i 3 时 n 还是 12 的变体会把 2 这个因子重复处理。为什么循环结束后还要判断一次n 1因为分解质因数时如果 n 本身是一个大于 sqrt(n) 的质数循环里的 i 最多到 sqrt(n) 就停了根本枚举不到它。比如 n 97循环结束 n 还是 97它就是个质因子必须继续乘一次。我手动模拟一个 n 84 的过程初始 res 84n 84。i 284 % 2 0res 84 / 2 * 1 42while 循环把 n 变成 21。i 321 % 3 0res 42 / 3 * 2 28while 循环把 n 变成 7。i 继续递增到 i 4 时发现 4 * 4 16 7循环退出。循环结束后 n 7 1res 28 / 7 * 6 24。所以 φ(84) 24。验证一下通式84 * (1 - 1/2) * (1 - 1/3) * (1 - 1/7) 84 * 1/2 * 2/3 * 6/7 24一致。3.2 批量预处理埃氏筛写法如果题目要预处理 1 到 N 的所有 φ 值再用单点分解就太慢了。这时可以用类似埃氏筛的思路把每个质数 p 对它的倍数都乘一次 (1 - 1/p)。const int MAXN 1000000; int phi[MAXN 1]; void get_phi_by_era(int n) { for (int i 1; i n; i) phi[i] i; // 先全赋成自己 for (int i 2; i n; i) { if (phi[i] i) { // 说明 i 还没被任何质数更新过i 是质数 for (int j i; j n; j i) { phi[j] phi[j] / i * (i - 1); // 处理所有含因子 i 的数 } } } }这个写法有个很妙的判断数组初始化时 phi[i] i。当循环到 i 时如果 phi[i] 还是 i说明 i 没有被任何更小的质数更新过那 i 一定是质数。可以用它去更新所有含有因子 i 的倍数。为什么这个代码正确考虑任意一个合数 m p1^a1 * p2^a2 * ... * pr^ar。当外层循环枚举到 p1 时内层循环会更新 phi[m]乘上 (1 - 1/p1)枚举到 p2 时又乘上 (1 - 1/p2)。每个不同质因子各处理一次这和通式完全一致。最终的 phi[m] 自然就是 m * ∏(1 - 1/p)。复杂度方面内层循环的总次数大约是 n * (1/2 1/3 1/5 ...)也就是 n 乘以质数倒数之和约等于 n log log n。对于 n 10^6 这个量级非常轻松。这个写法的优势是简单、不容易写错适合快速交卷。3.3 线性筛欧拉筛优化写法埃氏筛虽然简单但每个数可能被多个质因子分别更新比如 30 会被 2、3、5 各更新一次。如果用欧拉筛也就是线性筛可以做到每个合数只被筛一次总复杂度 O(n)。需要把求 φ 和线性筛质数合并在一起const int MAXN 1000000; int phi[MAXN 1]; int primes[MAXN]; bool isComp[MAXN 1]; int cnt; void euler_sieve(int n) { phi[1] 1; for (int i 2; i n; i) { if (!isComp[i]) { primes[cnt] i; phi[i] i - 1; // 质数的互质个数就是 i-1 } for (int j 0; j cnt (long long)i * primes[j] n; j) { int p primes[j]; int x i * p; isComp[x] true; if (i % p 0) { phi[x] phi[i] * p; // p 已经存在于 i 的质因子集合中 break; } else { phi[x] phi[i] * (p - 1); // p 是新质因子且和 i 互质 } } } }这里最关键的是两个公式的推导。当 p 是 i 的质因子时也就是说 i % p 0。设 i p^k * t其中 t 不含 p。那么 x i * p p^(k1) * t。x 的质因子集合和 i 完全相同只是 p 的指数多了 1。从通式看φ(x) x * ∏(1 - 1/q) i * p * ∏(1 - 1/q) φ(i) * p。所以这种情况 phi[x] phi[i] * p。当 p 不是 i 的质因子时gcd(p, i) 1直接用积性性质φ(x) φ(i * p) φ(i) * φ(p) φ(i) * (p - 1)。所以这种情况 phi[x] phi[i] * (p - 1)。那为什么要 break线性筛能保证每个合数只被筛一次靠的就是“只用最小质因子筛它”。当 i % p 0 时p 是 i 的最小质因子对于更大的 px i * p 的最小质因子仍然是 p而不是 p它应该在 i 更大时由 p 筛出来所以这里必须 break。如果少了 break复杂度退化的同时还会出现重复赋值表现就是答案错乱。我拿个具体数字过一遍i 4 时primes[0] 24 % 2 0所以 phi[8] phi[4] * 2 2 * 2 4然后 break。如果这里不 break继续用 p 3 去计算 phi[12] phi[4] * (3 - 1) 4但实际上 12 的最小质因子是 2它应该由 i 6、p 2 这条路径算出来也就是 phi[12] phi[6] * 2 2 * 2 4。虽然这次碰巧结果一样但筛法顺序被破坏了后续很多依赖最小质因子信息的操作都会出问题。3.4 怎么选复杂度与适用场景三种方法各有适用场景做题时先看数据范围再决定不要把时间浪费在过度优化上。方法时间复杂度空间复杂度适用场景试除法单次 O(√n)O(1)n 很大但只问一次或几次埃氏筛O(n log log n)O(n)批量预处理n ≤ 10^6线性筛O(n)O(n)批量预处理或者需要同时筛素数表、最小质因子我个人的选型习惯是如果题目只问一两个数直接用试除法代码短还不需要预处理数组如果询问次数超过 10 次或者 n 在 10^5 以上就乖乖预处理预处理时优先线性筛因为它顺手就把质数表、每个数的最小质因子都筛出来了后面很多题都用得上。埃氏筛虽然简单但是二次用到线性筛的场景时反而要多写一遍质数判断并不划算。4. 常见错误、高频题型与实战心得4.1 六个容易踩坑的细节第一个坑我先在前面反复强调过先除后乘。res res / i * (i - 1)和res res * (i - 1) / i看起来差不多实际差别很大。中间结果可能溢出而且 res 是否能被后面的 i 整除不一定有保证。我在实际调试里见过很多次就是因为多乘了一下导致越界结果全是负数。第二个坑是试除法里忘记把质因子除干净。比如算 φ(12)只处理了 i 2 没把 2 除干净下次 i 3 时还能被 2 整除就会把 2 这个因子重复用一次答案变成 12 * 1/2 * 1/2 * 2/3 4但正确答案是 4等等12 * 1/2 * 1/2 * 2/3 4而 φ(12) 4。这个例子碰巧是对的因为多乘一个 (1 - 1/2) 被后面的 2/3 抵消了不对φ(12)4 是正确而算出来也是4这只是巧合。换个例子 n8如果不除干净i2 时 res4n 还是 8循环结束 n81res4/8*73而 φ(8)4错误。总之不除净质因子会出现随机性错误必须养成 while 除尽的习惯。第三个坑是循环边界。i * i n这个写法在 i 比较大的时候 i * i 可能溢出 int。我在竞赛里特别喜欢用i n / i既避免了溢出又少写一次 long long 转换。如果坚持用乘法就写成(long long)i * i n。第四个坑是欧拉筛的 break 位置。break 必须放在i % p 0的分支里而且要在赋值完成之后。有些初学者图省事把 break 放在 if 外面结果每个合数被多个质因子重复筛到复杂度退化的同时 phi 值也可能被覆盖错误。第五个坑是忘了初始化 phi[1] 1。欧拉筛里如果你不初始化 phi[1]后面的很多推导虽然不会直接引用但题目里如果问到 φ(1)答案就错了。定义上 φ(1) 1这是约定但不是所有模板都会帮你写。第六个坑是没有特判 n 1。当 n 1 时很多和 φ 相关的推导会退化。比如求逆元、求 gcd(x, n) d 的计数都要先判断边界。实际题目里 n 1 通常很简单但往往就是这种边界数据最容易被卡。4.2 和欧拉定理配套的高频应用欧拉函数最重要的应用欧拉定理如果 gcd(a, n) 1那么 a^φ(n) ≡ 1 (mod n)。证明很简短设 a1, a2, ..., a_{φ(n)} 是模 n 的缩系也就是所有和 n 互质的剩余类。因为 gcd(a, n) 1所以 aa1, aa2, ..., a*a_{φ(n)} 仍然是模 n 的缩系。把两组数各自相乘得到 a^{φ(n)} * ∏ai ≡ ∏ai (mod n)两边约去和 n 互质的 ∏ai就得证了。欧拉定理带来的第一个直接推论是费马小定理当 n 是质数 p 时φ(p) p - 1所以 a^(p-1) ≡ 1 (mod p)。第二个推论是求乘法逆元如果 gcd(a, n) 1那么 a^(φ(n)-1) mod n 就是 a 在模 n 下的逆元。举个例子模 7 下求 3 的逆元φ(7) 6所以 3 的逆元是 3^5 mod 7 5验证 3 * 5 15 ≡ 1 (mod 7)正确。第三个应用是扩展欧拉定理用来做大指数降幂。当 b ≥ φ(m) 时a^b ≡ a^(b mod φ(m) φ(m)) (mod m)这个公式不需要 gcd(a, m) 1比欧拉定理本身适用范围更广。竞赛里经常出 a^b^c 这种层层嵌套的指数直接快速幂根本不行就是把指数一层层用扩展欧拉定理降下来。写个幂套幂题的时候你会发现 φ 函数简直无处不在。4.3 几条实战经验速查表最后我整理一张速查表把前面零散的经验浓缩进去刷题时可以直接对照。问题特征首选做法必须注意的点求单个 φ(n)n 最大 10^9试除法分解质因数先除后乘循环结束后处理剩余大质因子多次询问n 在 10^5 以上筛法预处理优先线性筛顺手保留素数表需要 [1, N] 全部 φ 值线性筛break 必须在 i % p 0 时马上执行统计 gcd(x, n) d 的 x 个数φ(n / d)先判断 d 是否能整除 n求 a^b mod mb 巨大扩展欧拉定理先判断 b 和 φ(m) 的大小关系求 a 在模 m 下的逆元a^(φ(m)-1) 快速幂必须先确认 gcd(a, m) 1写筛法后验算Σ φ(d) n随机取几个 n约数求和检查我个人刷题下来最大的感受是欧拉函数的代码模板三分钟就能背完真正拉开差距的是你能不能识别题目里的“互质”。很多题目包装复杂但读完题发现核心是“最简分数”“既约剩余系”“gcd 等于某值”这时候就要条件反射掏出 φ。最后再分享一个小技巧每次拿到欧拉函数相关题先别急着敲代码心里过三个问题。第一单点查询还是批量预处理第二n 的数据范围多大要不要开 long long第三题目里有没有幂运算需不需要同时用扩展欧拉定理降指数这三个问题想清楚了模板怎么选自然就清楚了。把证明的每一环都真正在大脑里过一遍比死记公式靠谱得多这也是我自己从“背了忘、忘了背”到真正记住欧拉函数整个过程里最有效的一条路。