企业官网建设流程全解析

学算法这几年我慢慢发现一个残酷的事实：很多知识点靠“多看几遍”是记不住的。尤其是数论这一块，欧拉函数、费马小定理、中国剩余定理，哪个单拎出来都是“看着眼熟，合上书就忘”。后来我彻底改了策略，每个公式必须亲手推一遍证明，推完之后再也没忘过。今天就把欧拉函数这份推导笔记完整整理出来，从定义、性质、证明到代码实现，一次性讲透。

欧拉函数这个名字在算法竞赛里出现的频率实在太高了，它本身是数论里最基础的工具之一，后面很多难题都会直接或间接用到它。无论是求逆元、算互质数个数、处理幂次降阶，还是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) = ∏_{i=1}^{k} φ(pi^{ai}) = ∏_{i=1}^{k} pi^{ai}(1 - 1/pi) = n · ∏_{i=1}^{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}。

这个集合有三个关键性质：

1. 个数确定：模 n 的简化剩余系恰好有 φ(n) 个元素。
2. 乘法封闭：如果 a、b 都与 n 互质，那么 gcd(a·b, n) = 1。因为质因子只有从 a 和 b 来，既然 a、b 都不含 n 的质因子，乘积也不含。
3. 消去律可用：如果 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^{a1+1}…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) = 1，1 到 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}”这种结论会有直觉，写起题来判断也快很多。欧拉函数是整个数论体系里少有的“证明一次，好处一辈子”的知识点，值得你花这个时间。