学算法这几年我慢慢发现一个残酷的事实很多知识点靠“多看几遍”是记不住的。尤其是数论这一块欧拉函数、费马小定理、中国剩余定理哪个单拎出来都是“看着眼熟合上书就忘”。后来我彻底改了策略每个公式必须亲手推一遍证明推完之后再也没忘过。今天就把欧拉函数这份推导笔记完整整理出来从定义、性质、证明到代码实现一次性讲透。欧拉函数这个名字在算法竞赛里出现的频率实在太高了它本身是数论里最基础的工具之一后面很多难题都会直接或间接用到它。无论是求逆元、算互质数个数、处理幂次降阶还是RSA一类密码学原理底层都是欧拉函数那一套。这篇文章适合刚接触数论、准备系统学习算法基础的人也适合刷题时总在欧拉函数上卡壳、想彻底搞懂原理的人。1. 先搞清楚欧拉函数在数论里的地位它到底解决了什么1.1 从一道“数数题”引入定义欧拉函数的定义其实特别朴素对正整数 nφ(n) 表示从 1 到 n 这些正整数里有多少个与 n 互质。比如 n 8从 1 到 8 里看1、3、5、7 都和 8 互质别的 2、4、6、8 都不行所以 φ(8) 4。n 5 是质数1、2、3、4 全和 5 互质所以 φ(5) 4也就是 p 是质数时 φ(p) p - 1。看起来就是个简单计数问题但为什么它在算法里地位这么高因为它本质上是在统计“模 n 的乘法群里到底有多少个元素”。在密码学里这个群的大小直接决定加密强度在算法题里凡是涉及“区间内有多少个数与某个数互质”的变形题兜兜转转都会回到欧拉函数上。1.2 为什么算法竞赛和密码学都绕不开它在题目中欧拉函数最直接的戏份是配合欧拉定理求乘法逆元。模 n 意义下a 的逆元是 a^{-1}满足 a · a^{-1} ≡ 1 (mod n)。当 n 是质数时逆元可以直接用费马小定理 a^{n-1} ≡ 1 (mod n) 推出来而费马小定理本质就是欧拉定理在质数情况下的特例。再往后很多整数分块、狄利克雷卷积、莫比乌斯反演的问题也会用到欧拉函数可以说它是数论题里绕不开的“地基”。对刷题的人来说掌握欧拉函数不能只会套公式你至少得能回答三件事公式长什么样、公式怎么来的、代码怎么写。下面我按这个顺序逐个说。2. 从质因数分解出发欧拉函数一般公式的两种推导路线欧拉函数最终结论是一个很漂亮的连乘公式。设 n 的唯一分解式是 n p1^{a1} · p2^{a2} · … · pk^{ak}其中 p1 到 pk 是互不相同的质因子那么φ(n) n · (1 - 1/p1) · (1 - 1/p2) · … · (1 - 1/pk)这个公式可以直接用于计算只要把 n 质因数分解就能求出欧拉函数值。但这个公式不能死背它背后有两条推导路线我都推一遍。2.1 容斥原理路线先算总数再减掉不互质的设 n 的质因子是 p1, p2, …, pk。在 1 到 n 的所有整数里怎么找与 n 互质的数直接用定义筛选太慢反过来算更聪明先统计总数 n再减掉所有“和 n 有公共质因子”的数。与 n 有公共质因子的数必然能被某个 pi 整除。于是思路就清晰了1 到 n 中能被 p1 整除的数有 n/p1 个能被 p2 整除的有 n/p2 个……但直接减会减重复。比如既能被 p1 整除又能被 p2 整除的数也就是能被 p1·p2 整除的数被减了两次要加回来一次。能被三个质因子乘积整除的数加减之间又多算了一次要再减掉。这就是典型的容斥原理。写成式子φ(n) n - ∑ n/pi ∑ n/(pi·pj) - ∑ n/(pi·pj·pl) … (-1)^k n/(p1p2…pk)观察一下它的结构每一项都是 n 除以若干个不同质因子的乘积。提取公因子 n 后括号里刚好是 (1 - 1/p1)(1 - 1/p2)…(1 - 1/pk) 的展开式。所以容斥结果就是φ(n) n · (1 - 1/p1) · (1 - 1/p2) · … · (1 - 1/pk)这个推导的好处是直接、严谨而且不需要借用其他结论。只要理解了容斥原理公式就不会忘。2.2 素因数幂次路线先啃下 p^k 这颗硬骨头另一条路线是从单个质数的幂次入手。先考虑 n p^k 这种特殊形式其中 p 是质数。此时从 1 到 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 · (1 - 1/p)算出这个特殊情形后再利用后面第 3 节要讲的积性性质把 n 分解成若干个互质部分相乘φ(n) φ(p1^{a1} · p2^{a2} · … · pk^{ak}) φ(p1^{a1}) · φ(p2^{a2}) · … · φ(pk^{ak})把每个 φ(pi^{ai}) pi^{ai} · (1 - 1/pi) 代进去乘起来恰好也是 n 乘以所有 (1 - 1/pi) 的形式。和容斥路线殊途同归。这两条路线是可互相印证的。个人建议最好两条都推一遍容斥路线帮你理解为什么公式是“乘上若干个 (1 - 1/p)”p^k 路线帮你迅速记住 φ(p^k) 的简洁形式。做题时经常遇到只含一个质因子幂次的情况比如模数是 p^k 时φ 直接就是 p^{k-1}(p-1)这时候单独记这个式子非常方便。3. 积性与乘法关系为什么只需要算质因数的贡献3.1 积性的严格证明——互素条件不能省欧拉函数有一个核心性质当 gcd(m, n) 1 时φ(m·n) φ(m) · φ(n)。这个性质叫积性是欧拉函数能“分别算再相乘”的根本原因。为什么成立用中国剩余定理的思想来看最直观。如果 gcd(m, n) 1那么模 mn 的一个剩余类可以唯一对应到一对剩余类 (a mod m, b mod n)。也就是说在模 mn 的整数环和模 m、模 n 的笛卡尔积之间存在一一对应。一个数 x 与 mn 互质当且仅当 x 与 m 互质且 x 与 n 互质。因此从 1 到 mn 中与 mn 互质的数的个数就等于“从 1 到 m 中与 m 互质的数的个数”乘以“从 1 到 n 中与 n 互质的数的个数”即 φ(mn) φ(m)φ(n)。这里要特别强调互素条件是必须的不能随便拆。举个例子φ(4) 2φ(2) 1但是 φ(8) 4而 φ(4)·φ(2) 2明显不相等。原因就是 gcd(4, 2) 2 ≠ 1。所以做题时看到 φ(mn) 想拆成 φ(m)φ(n)第一反应必须确认 gcd(m, n) 是否等于 1。3.2 用积性重写通用公式有了积性欧拉函数的计算路径就非常清晰了。只要把 n 质因数分解成标准形式然后φ(n) ∏_{i1}^{k} φ(pi^{ai}) ∏_{i1}^{k} pi^{ai}(1 - 1/pi) n · ∏_{i1}^{k}(1 - 1/pi)这就是为什么网上代码模板里都是“对每个质因子 p把 res 变成 res / p * (p - 1)”。因为 (1 - 1/p) 乘到 n 上等价于把 n 里的因子 p 消掉一次再乘上 (p - 1)。这个操作把所有质因子连乘起来就是欧拉函数值。顺便说一句积性的证明思路在数论其他地方也经常用到。比如后面学莫比乌斯函数 μ 时它的定义也是基于质因子个数的奇偶性处理方式一脉相承。把欧拉函数的积性吃透了后面学很多东西都会顺手很多。4. 欧拉定理证明从简化剩余系到取模运算的桥梁4.1 简化剩余系的三个核心事实在证明欧拉定理之前得先理解一个概念简化剩余系。模 n 的简化剩余系就是从 1 到 n 中挑出所有与 n 互质的数一共 φ(n) 个。比如模 8 的简化剩余系是 {1, 3, 5, 7}模 5 的简化剩余系是 {1, 2, 3, 4}。这个集合有三个关键性质个数确定模 n 的简化剩余系恰好有 φ(n) 个元素。乘法封闭如果 a、b 都与 n 互质那么 gcd(a·b, n) 1。因为质因子只有从 a 和 b 来既然 a、b 都不含 n 的质因子乘积也不含。消去律可用如果 gcd(c, n) 1 且 c·a ≡ c·b (mod n)那么可以两边同时消去 c得到 a ≡ b (mod n)。这个由同余定义可以直接推出因为 n | c(a - b)而 gcd(c, n) 1所以 n | (a - b)。这三条性质是欧拉定理证明的基石。4.2 a^φ(n) ≡ 1 (mod n) 的完整证明欧拉定理说的是若 gcd(a, n) 1则 a^{φ(n)} ≡ 1 (mod n)。证明分四步走第一步取模 n 的简化剩余系 {x1, x2, …, x_{φ(n)}}。第二步将每个元素都乘以 a得到 {a·x1, a·x2, …, a·x_{φ(n)}}。由于 a 和 xi 都与 n 互质根据乘法封闭性每个 a·xi 也与 n 互质。第三步证明这 φ(n) 个数在模 n 下两两不同。假设 a·xi ≡ a·xj (mod n)因为 gcd(a, n) 1根据消去律可得 xi ≡ xj (mod n)这与 xi、xj 是简化剩余系中不同的元素矛盾。所以它们两两不同。于是 {a·x1, a·x2, …, a·x_{φ(n)}} 仍然构成模 n 的一组简化剩余系只不过顺序可能打乱了。第四步把两组简化剩余系各自乘起来乘积应当同余(a·x1) · (a·x2) · … · (a·x_{φ(n)}) ≡ x1 · x2 · … · x_{φ(n)} (mod n)左边提出 φ(n) 个 a得到 a^{φ(n)} · (x1·x2·…·x_{φ(n)}) ≡ x1·x2·…·x_{φ(n)} (mod n)。因为 x1·x2·…·x_{φ(n)} 与 n 互质再次利用消去律约掉最终得到 a^{φ(n)} ≡ 1 (mod n)。证明完毕。这套思路非常经典值得反复品味。它没什么高深技巧核心就是“两个简化剩余系可以互相转化”。4.3 费马小定理欧拉定理的直接推论当 n 是质数 p 时φ(p) p - 1欧拉定理直接变成费马小定理a^{p-1} ≡ 1 (mod p)其中 gcd(a, p) 1。这个推论在算法竞赛里的出镜率比欧拉定理本身还高。最典型的应用就是求逆元当模数是质数时a 的逆元是 a^{p-2} mod p。因为 a·a^{p-2} a^{p-1} ≡ 1 (mod p)。很多题目的模数就是 998244353 这种大质数所以这个结论几乎每天都在用。欧拉定理更大的价值在于它揭示了一个事实模 n 乘法群中每个元素的幂次在以 φ(n) 为周期循环。这意味着在计算 a^b mod n 时指数可以模 φ(n) 缩小这就是后面说的欧拉降幂的基础。5. 代码层面单点求值与线性筛的工程实现数学推导说完了接下来是实战环节。欧拉函数的代码实现主要分两种场景单次求一个数的欧拉函数值和预处理 1 到 n 所有数的欧拉函数值。5.1 单点计算质因数分解模板与时间复杂度如果只求一个数 n 的欧拉函数值思路很直接质因数分解套公式。模板如下// 单点求欧拉函数时间复杂度 O(sqrt(n)) int euler_phi(int n) { int res n; for (int i 2; i * i n; i) { if (n % i 0) { // 找到一个质因子 i res res / i * (i - 1); // 等价于 res * (1 - 1/i)先除后乘防溢出 while (n % i 0) { // 把这个质因子从 n 里全部除掉 n / i; } } } if (n 1) { // 最后剩下的 n 本身是一个大于 sqrt 的质因子 res res / n * (n - 1); } return res; }这里有几个实现细节值得说明。第一循环写到 i * i n 即可因为一个数的质因子里最多只有一个大于它的平方根。把所有小因子除干净后最后剩余的 n 必然是大于 sqrt 的质因子所以要单独处理一次。第二res res / i * (i - 1) 这个写法要先除再乘不要写成 res * (i - 1) / i。因为整数除法会先截断(i - 1) / i 在整数中等于 0结果就变成 0 了。先除再乘也不会有精度问题因为 res 一定能被 i 整除。第三处理完一个质因子后用 while 循环把 n 里所有该因子除干净防止后面重复统计。5.2 线性筛预处理O(n) 求出 1 到 n 的所有欧拉函数值如果多次查询不同数的欧拉函数值每次都质因数分解就太慢了。竞赛里更常见的做法是预处理一张表用线性筛在 O(n) 时间内求出 1 到 n 的所有欧拉函数值。线性筛的思想是每个合数只会被它的最小质因子筛掉一次保证每个数只处理一次从而让整体复杂度是线性。利用线性筛求欧拉函数的模板如下const int MAXN 1e6 5; int phi[MAXN]; // 欧拉函数表 int primes[MAXN]; // 质数表 int cnt 0; // 质数数量 bool isComposite[MAXN]; // 标记合数 void precompute_phi(int n) { phi[1] 1; // 约定 phi[1] 1 for (int i 2; i n; i) { if (!isComposite[i]) { primes[cnt] i; phi[i] i - 1; // 质数的欧拉函数值是 i-1 } for (int j 0; j cnt i * primes[j] n; j) { isComposite[i * primes[j]] true; if (i % primes[j] 0) { // primes[j] 是 i 的最小质因子 // 此时 i * primes[j] 与 i 的质因子集合相同 phi[i * primes[j]] phi[i] * primes[j]; break; } else { // primes[j] 与 i 互质利用积性 phi[i * primes[j]] phi[i] * (primes[j] - 1); } } } }很多初学者卡在这个模板里搞不懂两个分支的 phi 是怎么推导出来的。我详细解释一下。第一种情况i % primes[j] 0说明 primes[j] 是 i 的因子。设 i 的质因数分解是 p1^{a1}…pk^{ak}且 p1 primes[j]。那么 i · primes[j] 的分解是 p1^{a11}…pk^{ak}质因子集合和 i 完全相同。所以从公式 φ(n) n∏(1 - 1/p) 来看φ(i·primes[j]) 和 φ(i) 的区别只是最前面的系数从 i 变成 i·primes[j]连乘部分不变。因此 φ(i·primes[j]) φ(i) · primes[j]。第二种情况i % primes[j] ! 0说明 primes[j] 不是 i 的因子因此 gcd(i, primes[j]) 1。利用积性φ(i·primes[j]) φ(i) · φ(primes[j]) φ(i) · (primes[j] - 1)。理解了这两个分支线性筛的代码就不是死记硬背了。另外注意 break 的条件是 i % primes[j] 0这样保证每个合数只被最小质因子筛掉一次这是“线性”的关键。5.3 欧拉定理在求逆元中的工程用法求逆元的场景在组合数计算里极为常见。模 p 是质数时a 关于模 p 的逆元为 a^{p-2} mod p配合快速幂就能在 O(log p) 时间内求出。// 快速幂模板 long long mod_pow(long long a, long long b, long long m) { long long res 1 % m; while (b 0) { if (b 1) res res * a % m; a a * a % m; b 1; } return res; } // 模质数 p 下求 a 的逆元 long long mod_inverse_prime(long long a, long long p) { return mod_pow(a, p - 2, p); }如果模数不是质数求逆元就要用扩展欧几里得算法或者要求 gcd(a, n) 1 时利用欧拉函数a^{-1} ≡ a^{φ(n)-1} (mod n)因为 a · a^{φ(n)-1} a^{φ(n)} ≡ 1 (mod n)。这个式子理论上成立但实际中我们都先对 n 分解质因数再决定用哪条路因为扩展欧几里得的常数更小而且不用拆模数。6. 做题时真正需要留意的几个细节和坑6.1 φ(1) 的约定与边界情况欧拉函数对 φ(1) 的约定是 φ(1) 1因为 gcd(1, 1) 11 到 1 中和 1 互质的数只有 1 自己。刷题时很多人会忘记初始化 phi[1]导致 n 1 的特判挂掉。最常见的场景是线性筛里单独给 phi[1] 赋值否则后面的某些递推依赖会出错。如果题目里 n 的范围包括 1一定要在代码里显式处理。另外有些题问的是前 n 项欧拉函数和这时候需要把 phi[1] 1 算进去不要漏。6.2 欧拉降幂的适用条件欧拉降幂是欧拉定理的一个重要扩展专门用来处理指数巨大的情况比如计算a^b mod m其中 b 可能大到 10^{1000000}。当 gcd(a, m) 1 时可以直接用欧拉定理把指数缩小a^b ≡ a^{b mod φ(m)} (mod m)。但当 gcd(a, m) ≠ 1 时这个结论不成立需要用扩展欧拉降幂公式如果 b ≥ φ(m)则 a^b ≡ a^{b mod φ(m) φ(m)} (mod m)。注意这个公式有两个前提一是 b 必须大于等于 φ(m)二是加上的 φ(m) 不能省略。很多题解里直接写 a^b a^{b mod φ(m)}那是默认了 gcd(a, m) 1。遇到不互质的情况还这么写就会出大问题。所以刷题时看到指数极大的题我的习惯是先把 φ(m) 求出来然后比较指数和 φ(m) 的大小再决定用哪个公式。6.3 从欧拉函数延伸出去的常见考点欧拉函数很少单独考更多是作为中间工具出现。常见的有欧拉函数前缀和定义 S(n) φ(1) φ(2) … φ(n)。用线性筛预处理 phi 数组后一次循环求前缀和即可。但很多题目 n 上限是 10^{11}这时就需要莫比乌斯反演配整除分块来求前缀和那是进阶内容。gcd 计数问题形如“求 1 到 n 里 gcd(x, n) d 的 x 个数”可以转化为 gcd(x/d, n/d) 1 的个数答案就是 φ(n/d)。如果题目要枚举 d每个 d 求一次 φ复杂度往往不够需要在外层枚举 n 的因子再算。和莫比乌斯函数的关系欧拉函数满足 Dirichlet 卷积恒等式 φ μ * id展开写就是 n ∑_{d|n} φ(d)。这个恒等式也很有用比如求互质有序对个数时就能派上用场。6.4 实际编写代码时容易踩的坑最后分享几个我在实际写题中踩过的坑。一个是数据类型。欧拉函数模板里 res 初始化为 n但 n 的范围如果到 10^{12}int 就不够用了。那时候 res 要开 long long分解质因数的循环变量 i 也要开 long long否则 i * i 都可能溢出成负数死循环。另一个是线性筛的边界控制。内层循环条件 j cnt i * primes[j] n 不能写成 i * primes[j] n j cnt因为 i * primes[j] 可能先溢出等判断 j cnt 时已经晚了。顺序写错在最坏情况下会导致数组越界或者结果错误排查起来很费劲。还有一个容易被忽略的性能问题如果题目有多组询问但 n 的最大值固定直接用线性筛预处理所有可能的 phi 是最省事的。如果每组数据 n 都不同且 n 很大筛 1 到 maxN 反而浪费这时候应该对每个 n 使用 O(√n) 的单点求法。所以做题前先分析一下数据范围再决定用哪套模板不是所有时候都无脑上线性筛。7. 回看“每日一遍”怎么记才不会忘回到标题里那句“每日一遍算法再见”。说实话欧拉函数这个知识点光靠“每日一遍”抄公式是没用的。我今天特意把推导过程完整写出来就是希望大家换个记法。我自己现在回忆欧拉函数脑子里浮现的是三条逻辑链第一φ(p^k) p^k - p^{k-1}这是从“不互质就是 p 的倍数”数出来的第二积性拆解互质才能拆拆完每个因子套第一个公式第三欧拉定理简化剩余系乘 a 之后还是简化剩余系。这三条链想清楚了公式、定理、代码都是顺手带出来的不用背。最后分享一个小习惯我每次学完一个数论函数都会专门写一个测试程序把 n 从 1 到 20 的 φ(n) 手算一遍和程序跑一遍对着看。手算几个数之后你对“为什么质数得 p-1”“为什么 p^k 要减 p^{k-1}”这种结论会有直觉写起题来判断也快很多。欧拉函数是整个数论体系里少有的“证明一次好处一辈子”的知识点值得你花这个时间。
