企业官网建设流程全解析

1. 内容整体设计与思路拆解

1.1 欧拉函数是什么——一个“计数问题”的角度

欧拉函数，符号写作 φ(n)，核心定义只有一句话：从 1 到 n 之间，与 n 互质的正整数的个数。它做的事情本质上是一个计数问题，比如 φ(6) = 2，因为 1 到 6 里面，只有 1 和 5 与 6 互质；φ(10) = 4，对应 1、3、7、9 这四个数。

在数论和算法竞赛里，这个函数出现频率极高。求逆元要它，欧拉降幂要它，很多 gcd 相关的计数题绕一圈也会回到它。更直白地说，欧拉函数是连接初等数论和算法的一个枢纽，你可以在很多中等难度以上的题目里看到它的影子。

我见过很多选手的困境是这样的：会背公式 φ(n) = n × (1 - 1/p₁) × ... × (1 - 1/pₖ)，也会用代码枚举质因数把它求出来，但一旦遇到需要推式子、需要把 φ 放进容斥或莫比乌斯反演的场景，就开始卡壳了。原因很简单，公式是背的，不是自己推的，所以永远不知道这个公式的边界在哪，也不知道它为什么不能随便拆。

1.2 为什么还要“详细证明+推导”

市面上讲欧拉函数的文章，大多数是“定义 + 公式 + 代码”三段式，证明要么一笔带过，要么直接省略。可问题在于：欧拉函数的推导过程，本身就是一套值得反复练习的数论思维模板。

从 1 到 n 的整数集合出发，把“不互质”的数踢掉，这是容斥原理；把 n 拆成素数幂的乘积，然后把每个部分单独拿出来分析，这是积性函数的分解思路；证明 φ(mn) = φ(m)φ(n) 需要利用模运算和中国剩余定理的映射关系，这是数论中极其常用的双射构造手法。这些工具单独拿出来都很基础，但合在一起，就是解决一大类数论问题的底层思维方式。

所以这篇博客我打算把推导过程完整走一遍，从直觉上的容斥理解，到严格的质因数分解证明，再到代码实现和竞赛应用。读完以后你不仅能写出来欧拉函数，还能明白它为什么长这个样子。

1.3 和“每日一遍，算法再见”对应的学习路径

“每日一遍，算法再见”这个标题，我特别有共鸣。算法的学习没有捷径，核心公式和推导过程需要反复过脑子，过到形成条件反射为止。但“每日一遍”不是让你每天重新抄一遍公式，那是假努力。

真正的循环应该是这样的：第一天理解定义和证明；第二天不看资料，自己从头推一遍公式，卡住了就回头翻；第三天开始写代码，先用单点求法，再上线性筛；第四天找两道应用题，把欧拉函数放进场景里用；第五天回顾错题和踩坑记录。按这个节奏走下来，欧拉函数基本就焊在脑子里了。

2. 欧拉函数的三种理解路径

2.1 容斥视角：从“不互质”反推

从定义出发，要数出 1 到 n 之间有多少个互质的数，最直接的想法是从总数 n 里减去与 n 不互质的数。假如 n 只有一个质因子 p，那么 1 到 n 之间有多少个数是 p 的倍数？显然是 n/p 个，所以互质个数就是 n - n/p = n × (1 - 1/p)。

拓展到两个质因子 p 和 q，这时候要小心，减掉 p 的倍数和 q 的倍数会重复减掉同时是 p 和 q 的倍数（也就是 p×q 的倍数）的数。所以需要容斥：总数 n - n/p - n/q + n/(pq) = n × (1 - 1/p) × (1 - 1/q)。

这个思路非常直观，而且它给了我们一个很重要的直觉：欧拉函数的乘积公式本质上就是容斥原理的另一种写法。当你把 n = ∏ pᵢ^{aᵢ} 的所有质因子都列出来，对每个质因子都做一次“剔除”操作，展开之后就是上面的容斥式，合并同类项后得到 φ(n) = n × ∏(1 - 1/pᵢ)。

不过从算法实现的角度来说，容斥视角不是最高效的计算路径，但它能帮你快速判断一些边界情况，比如为什么 φ(1) = 1（因为 1 到 1 之间只有 1，且 gcd(1,1) = 1）。

2.2 积性函数视角：拆成素数幂再拼起来

容斥能解释公式，但严格证明欧拉函数在互质条件下满足 φ(mn) = φ(m)φ(n) 时，我们需要更结构化的方式。这里的核心是：欧拉函数是积性函数，当 m 和 n 互质时，φ(mn) = φ(m)φ(n)。

为什么强调“互质”这个条件？因为如果不互质，这个等式就不成立。举一个最经典的例子：φ(4) = 2，而 φ(2) × φ(2) = 1 × 1 = 1，两者不相等。4 和 2 不互质，直接拆就翻了。

有了积性性质以后，我们只需要研究素数幂单独的情况。对于素数 p 的 k 次幂 p^k，1 到 p^k 之间与 p^k 不互质的数，恰好就是 p 的倍数，一共有 p^{k-1} 个。所以：

φ(p^k) = p^k - p^{k-1} = p^k × (1 - 1/p)。

把 n 分解成 n = p₁^{a₁} * p₂^{a₂} * ... * pᵣ^{aᵣ}，因为所有 pᵢ^{aᵢ} 两两互质，所以：

φ(n) = φ(p₁^{a₁}) × φ(p₂^{a₂}) × ... × φ(pᵣ^{aᵣ}) = p₁^{a₁}(1 - 1/p₁) × p₂^{a₂}(1 - 1/p₂) × ... × pᵣ^{aᵣ}(1 - 1/pᵣ) = n × ∏(1 - 1/pᵢ)。

这个推导路径，是“积性函数”这个更宏大的数论框架下的一个具体案例。以后遇到其他积性函数（比如莫比乌斯函数 μ、约数和函数 σ），都可以沿用这个思路：先看素数幂，再用互质条件拼回去。

2.3 剩余系视角：和简化剩余系的关系

第三种理解方式是从同余的角度看。模 n 的剩余类一共有 n 类，其中与 n 互质的那些剩余类，组成了模 n 的简化剩余系。简化剩余系的元素个数，恰好就是 φ(n)。

这个视角在证明欧拉定理的时候非常关键。假设 a 与 n 互质，那么 a 乘以简化剩余系里的每个元素，得到的集合还是简化剩余系（这是模运算保互质性的结果）。把所有元素乘起来，可以抵消掉公共部分，得到 a^{φ(n)} ≡ 1 (mod n)。这就是欧拉定理的核心证明逻辑。

我在实际做题中发现，这三种视角并不是孤立的，它们经常在同一道题里交替出现。用容斥做计数，用积性做拆分，用剩余系做映射，这才是欧拉函数被“用活”的状态。

3. 从公式到代码：单点求解的实操过程

3.1 单点求解的数学化简过程

要计算一个具体的 n 的欧拉函数值，最稳妥的手算方式就是质因数分解。比如 n = 100，先分解得到 100 = 2² × 5²，然后代入公式：

φ(100) = 100 × (1 - 1/2) × (1 - 1/5) = 100 × 1/2 × 4/5 = 40。

这里有一个小细节值得注意：直接按公式展开会得到 n / p₁ / p₂ × (p₁-1) × (p₂-1)，写成代码的时候，如果先乘 (p-1) 再除 p，就能避免 n 被整除截断导致的精度问题。因为 φ(n) 一定是整数，但在中间计算时如果先除可能产生小数或者整除误差，所以代码里先除后乘或者先乘后除要看数据范围决定。

比如 n = 10，质因子只有 2 和 5。如果代码写成 n = n / 2 * 1 = 5，然后再 5 / 5 * 4 = 4，结果正确；但如果写成 n = n * (2-1) / 2 * (5-1) / 5，10 × 1 / 2 × 4 / 5，由于整数除法舍去小数，10/2=5，5×4=20，20/5=4，也没有问题。可换一个极端例子 n = 3，只有因子 3，n * (3-1) / 3 = 3×2 / 3 = 2，答案正确。对于较小范围，先乘后除没有风险，但要注意乘法可能溢出。我习惯先除后乘，因为每个质因子的 (1-1/p) 本质上就是把 n 里对应素数的那部分贡献去掉，先除会让中间结果保持较小的量级。

3.2 C++ 单点求解实现

以下是单点求欧拉函数的经典写法，时间复杂度 O(√n)：

int phi(int n) { int res = n; for (int p = 2; p * p <= n; ++p) { if (n % p == 0) { res = res / p * (p - 1); // 等价于 res *= (1 - 1/p) while (n % p == 0) n /= p; // 把质因子 p 全部除掉 } } if (n > 1) res = res / n * (n - 1); // 处理大于 sqrt(n) 的质因子 return res; }

这段代码的核心逻辑是枚举可能的质因子，找到以后先更新 res，再用 while 循环把 n 里这个质因子全部除干净。最后一步尤其关键：如果 n 还剩一个大于 √原n 的质因子，它一定会以“剩余 n > 1”的形式出现，这时候再乘一次 (n-1)/n 即可。

我第一次写这个函数的时候，就漏了最后那个if (n > 1)的判断，导致 φ(6) 算出来是 2 而不是 2？实测就出错了。所以这个细节我印象特别深。

3.3 关于时间复杂度为什么是 O(√n)

这个循环的终止条件是 p * p <= n，但注意循环体内部会不断缩小 n，所以实际循环次数远小于 √n。严格分析这个问题，最坏情况发生在 n 是素数时：循环会一直跑到 p * p > n，也就是大约 √n 次。所以最坏复杂度 O(√n)。

单点求解在 n 是 int 范围（约 2.1 × 10⁹）内非常轻松，但如果 n 达到 10¹²（long long 范围），循环次数最多 10⁶，单次查询还能接受，多次查询就会超时。这时候要么预计算质数表去加速质因子枚举，要么改用后面的线性筛方法。

4. 线性筛欧拉函数：预处理才是竞赛日常

4.1 为什么需要批量求解

单点求法虽然好写，但很多题目要的是区间统计或者多次查询，比如“求 1 到 n 所有数的欧拉函数之和”，或者“对数组每个元素取 φ 再进行下一步计算”。如果对每个数单独做质因数分解，总复杂度会爆炸。这时候就需要一种 O(n) 的预处理方式，一次性把 φ(1) 到 φ(n) 全部算出来。

线性筛之所以能做到 O(n)，是因为每个合数只会被它的最小质因子筛掉一次，不会重复标记。在筛的过程中，我们可以顺便求出每个数的 φ 值，这就叫“线性筛欧拉函数”。

4.2 线性筛的思想与代码

先看核心代码：

const int MAXN = 1000000; int phi[MAXN + 5]; int primes[MAXN + 5]; bool isComp[MAXN + 5]; int cnt = 0; void getPhi(int n) { phi[1] = 1; for (int i = 2; i <= n; ++i) { if (!isComp[i]) { primes[cnt++] = i; phi[i] = i - 1; // 质数的 phi 就是 i-1 } for (int j = 0; j < cnt && i * primes[j] <= n; ++j) { isComp[i * primes[j]] = true; if (i % primes[j] == 0) { phi[i * primes[j]] = phi[i] * primes[j]; break; } else { phi[i * primes[j]] = phi[i] * (primes[j] - 1); } } } }

这段代码初看容易懵，我拆开讲。

首先，phi[1] = 1是定义，也是边界条件。对于每一个 i，如果它还没被标记为合数，那它就是质数，它的 φ 值就是 i - 1，同时把它放进质数表。

其次，内层循环用质数表里的 primes[j] 去标记合数。当i % primes[j] == 0时，说明 primes[j] 是 i 的因子，也是 i * primes[j] 的最小质因子。这时候 i * primes[j] 和 i 的质因子集合完全相同，只是某个质因子的指数加了 1，所以 φ 值按 φ(i * p) = φ(i) * p 来更新。

如果i % primes[j] != 0，说明 p 是新增的质因子，且 p 与 i 互质，利用积性性质：φ(i * p) = φ(i) * φ(p) = φ(i) * (p - 1)。

更新完以后，一旦遇到i % primes[j] == 0就要 break。这一步是线性筛的精髓，它保证每个合数只会被它的最小质因子筛到，避免了重复标记，从而把整体复杂度压到 O(n)。

4.3 对拍验证与调试技巧

写完线性筛以后，我强烈建议你写一个小对拍程序，把线性筛的结果和单点 O(√n) 求解的结果对照一遍，范围选 1 到 1000 就够。这样能快速排查两大类 bug：一类是边界问题（比如 n=1、n=2 时数组越界），另一类是递推公式写反了（把乘 p 和乘 p-1 弄混）。

我当时的对拍代码大概是这样的：

bool check(int n) { for (int i = 1; i <= n; ++i) { int val = phiOne(i); if (val != phi[i]) { cout << "mismatch at " << i << " got " << phi[i] << " expected " << val << endl; return false; } } return true; }

这类验证代码写完之后，如果你把 MAXN 调到 10⁷，再看看筛法耗时，你会发现 O(n) 和 O(n log log n) 之间的差别在数据量大时非常明显。这也是为什么“能线性筛就别用单点爆算”成为了一条实用经验。

5. 欧拉定理、欧拉降幂与其他应用

5.1 欧拉定理与费马小定理的关系

欧拉定理说的是：如果 gcd(a, n) = 1，那么 a^{φ(n)} ≡ 1 (mod n)。这个定理的直接推论，就是求模逆元：a 的逆元为 a^{φ(n)-1} mod n。

费马小定理是欧拉定理的特例，当 n 是质数 p 时，φ(p) = p - 1，于是 a^{p-1} ≡ 1 (mod p)。很多人在看到“a^{p-2} 就是 a 在模 p 下的逆元”这个结论时，可能并不知道它其实是欧拉定理的产物，但如果从欧拉函数的视角看，这个式子就变得非常自然。

欧拉定理的证明过程本身就很有意思：把模 n 的简化剩余系记为 a₁, a₂, ..., a_{φ(n)}，因为 gcd(a, n) = 1，所以 a×a₁, a×a₂, ..., a×a_{φ(n)} 也构成模 n 的简化剩余系。两组元素乘积相同，于是约去公共因子，得到 a^{φ(n)} ≡ 1。

这个证明我第一次看的时候觉得很巧妙，后来自己推导一遍才发现，关键只在于“互质元素乘以一个互质的数还是互质的”，以及“简化剩余系在乘法下封闭”这两个性质。这就是前面说的剩余系视角，它比死记定理管用得多。

5.2 欧拉降幂到底在解决什么问题

欧拉降幂解决的是这样一类问题：求 a^b mod p，但 b 非常大，大到无法直接用快速幂计算指数（例如 b 是一个长度达到 10⁶ 的十进制大数）。这时利用扩展欧拉定理：

当 b ≥ φ(p) 时，a^b ≡ a^{b mod φ(p) + φ(p)} (mod p)。

注意，这里不需要 gcd(a, p) = 1，这是扩展欧拉定理比原始欧拉定理更强的地方。使用时需要判断 b 是否大于等于 φ(p)，然后读入大数 b 时模 φ(p) 并同时记录是否已经超过 φ(p)。

很多初学者会把欧拉降幂和普通模运算搞混：a^b mod p 不能简简单单对指数取模，因为指数是 mod φ(p)，底数才是 mod p。我第一次做这类题时，直接对 b 模了 p，结果样例都过不了。这个坑，必须记录下来。

5.3 逆元、gcd 计数等经典场景

除了降幂，欧拉函数还大量出现在组合计数问题中。举一个常见套路，求 1 到 n 之间与 n 互质的数的个数，直接就是 φ(n)。更进阶一点，求 ∑_{i=1}^{n} gcd(i, n) 这类式子，可以用枚举 gcd 的取值 d 来做：只有当 gcd(i, n) = d 时，i/d 和 n/d 互质，所以个数是 φ(n/d)。于是：

∑_{i=1}^{n} gcd(i, n) = ∑_{d|n} d × φ(n/d)。

这个式子看起来简单，但它把 gcd 计数问题转化成了枚举 n 的因子和查 φ 表的问题，在很多题目里都能直接套。类似的还有 ∑_{i=1}^{n} lcm(i, n) 的变形，先利用 lcm = ab/gcd 展开，再套上面的结论。

再比如，求解线性同余方程 a×x ≡ 1 (mod m) 时，如果 gcd(a, m) = 1，可以用快速幂求 a^{φ(m)-1} mod m。如果 m 很大但能分解，先算 φ(m) 再做快速幂。如果 m 是质数，直接 a^{m-2} 就行。这些都是欧拉函数在模板题里的高频应用。

6. 常见问题与排查技巧实录

6.1 边界情况：n = 1 别翻车

φ(1) 按定义是 1，因为 1 与 1 互质。但在很多题目里，φ(1) 是否参与计算需要专门判断。比如在欧拉降幂中，p = 1 时任何数模 1 都等于 0，但 φ(1) = 1，如果代码里没有特判，可能死循环或者结果错误。

另外，线性筛里如果 n = 1，循环从 2 开始自然就不会执行，但 phi[1] 必须提前置 1。这是个很容易被忽略的细节。

6.2 筛法数组开多大、循环范围怎么定

线性筛的数组长度，取决于 n 的最大值。注意int primes[MAXN]里素数个数约为 n / ln n，远小于 n，但为了保险，数组长度开到 n 就行。循环范围是i <= n，内层是i * primes[j] <= n。这个边界写错，要么数组越界，要么漏筛合数。

我还犯过一个经典错误：把内层循环写成j < cnt且没有限制i * primes[j] <= n，导致数组下标越界。修的时候加了个&&条件就好了。调试方法就是打印一遍 primes 数组，看最后一个元素是不是大于 n，立刻能发现问题。

6.3 int 溢出、取模细节等实际踩坑

单点求 φ 时，res * (p - 1)可能溢出 int，尤其 n 接近 int 上限时。所以 res 建议用 long long，或者每一步都保持先除后乘。在线性筛中，i * primes[j]也可能溢出 int，需要写成1LL * i * primes[j] <= n或者直接给 i 和 primes[j] 开 long long。

取模方面，欧拉降幂里 b 是一个大数时，读入过程要边读边模 φ(p)，同时用一个 bool 标记是否已经超过 φ(p)。如果 b 没有超过 φ(p)，就不能套扩展欧拉定理直接降幂，而应该老老实实直接快速幂。这个地方尤其容易在数据比较刁钻时出错。

6.4 一个高频出错的“互质”判断题

我见过不少人在题目里默认 gcd(a, n) = 1，然后用费马小定理求逆元。但实际数据里 a 可能是 n 的倍数。如果 gcd(a, n) > 1，逆元根本不存在，此时快速幂算出来的“逆元”没有任何意义。

结论是：用欧拉定理和费马小定理求逆元之前，一定要先判断互质。如果题目没有保证互质，那就不能直接套，得考虑扩展欧几里得算法或者转换成其他做法。这个判断花不了几行，能帮你避开一大半 WA。

7. 把“每日一遍”变成“肌肉记忆”

7.1 我自己的刷题节奏建议

我的建议是，把欧拉函数的复习拆成三个层次。第一层是公式默写：每天随机选几个 n 手算 φ(n)，对着质因数分解验算；第二层是证明复述：不看书，自己从定义出发推出 φ(n) = n ∏(1 - 1/p)；第三层是代码速写：用五分钟把单点求法和线性筛默写一遍，不允许看模板。

“每日一遍”不是每天重复简单的抄写，而是每次都比上一次多深入一点。比如第一周只看定义，第二周试着自己证明积性，第三周去做两道欧拉降幂的题，第四周尝试把 φ(n/d) 套进 gcd 计数里。这样循环几周，欧拉函数相关的套路基本就全面覆盖了。

7.2 一道练习题的思路

最后留一道我经常推荐给学生的练手题：求 1 到 n 里所有与 n 互质的数的和。暴力是 O(n)，但用欧拉函数可以做到 O(√n + 枚举因子) 甚至 O(√n)。关键在于当 gcd(i, n) = 1 时，gcd(n - i, n) = 1 也成立，也就是说互质的数可以两两配对成 n。如果 φ(n) 是偶数，配对数就是 φ(n)/2，和为 n × φ(n)/2；如果 φ(n) = 1（即 n = 1 或 2），需要单独处理。

这道题我当年第一次做的时候，没想到配对法，硬是枚举了所有 i 去判断 gcd，复杂度高得离谱。后来意识到这只是欧拉函数定义的一个直接推论，反思了很久。

7.3 一些经验体会

我个人的体会是，欧拉函数是所有数论函数里最应该“亲手推一遍”的。背公式的人看到 φ(2) × φ(2) ≠ φ(4) 会觉得是“特例”，推过证明的人会立刻意识到这是因为 2 和 4 不互质，积性条件不满足。这种差别会在做难题时被无限放大。

回到“每日一遍，算法再见”，算法学习本质上就是反复对抗遗忘的过程。欧拉函数推导和代码实现都不难，但真正能在赛场上快速反应过来，靠的还是平时的多遍复盘。把证明、公式、代码、应用场景串成一条线，每次复习都从定义重新出发，比死记硬背高效得多。

最后分享一个小技巧：我在电脑桌面上放了一个文本文件，里面只有一句话——φ(n) = n ∏(1 - 1/p)。每次打开电脑看到它，就在脑子里快速过一遍：“为什么有这个公式？不互质的数怎么剔？怎么在代码里实现？”想通了就关掉，想不通就翻博客。坚持下来，这五个问题就成了条件反射。