数论在CSP-S提高组里一直是个“看着不难、一写就错”的模块。很多选手能把快速幂背得很熟，可一旦指数变成10^18，或者模数不再是1000000007那种常见质数，就不知道怎么办了。这时候，欧拉函数和欧拉定理就该登场了。这篇文章不是把定义抄一遍，而是带着你从“为什么要定义它”开始，一路推到线性筛的完整代码、定理的证明直觉，以及几类真正会在赛场上遇到的题。不管你是正在备赛CSP-S的选手，还是刚接触数论基础、想系统补课的自学者，只要已经会质因数分解和快速幂，这篇文章就能直接往下读。
1. 为什么CSP-S选手绕不过欧拉函数：先讲清楚它解决什么问题
1.1 指数大到你不敢快速幂的题目，长什么样
先说一个我在带学生时常举的例子：求 3^1000000000 mod 2024。
暴力的思路是把3连乘十亿次，这显然不可能。快速幂可以解决指数是long long范围的问题，也就是 b ≤ 9×10^18 还能跑，但如果题目把指数藏在字符串里，或者指数本身是由递推算出来的超大数，甚至指数是别人给你的“n的n次方”，这时候直接快速幂也力不从心。
你需要一个办法把指数“缩小”，而缩小的工具就是欧拉定理。我对学生的要求从来不是“能背出公式”，而是看到这类题目能立刻想到：指数的规模决定我要不要降幂，模数是否和底数互质决定我能不能用欧拉定理。这两句话想清楚，题目就已经解决一半了。
1.2 提高组数论题的基本盘：考点其实很固定
CSP-S的数论题不会考数学竞赛那种偏题怪题，翻来覆去就是质数判定、质因数分解、最大公约数、快速幂、线性筛、逆元、组合数取模这些点，而欧拉函数和欧拉定理正好卡在这些点的交汇处。
举个例子，很多题目要求你计算组合数 C(n,k) mod p，其中n和k很大但p是一个小质数。做法是用卢卡斯定理，但卢卡斯定理依赖逆元，而逆元本质上就是在用费马小定理。一旦模数不是质数，费马小定理失效，你必须回到更一般的欧拉定理。再比如“求1到n中与n互质的数的个数”这类题，直接就是在考欧拉函数的定义。
所以我的结论是：欧拉函数和欧拉定理不是数论里某个孤立的技巧，而是连接质因数分解、逆元、快速幂、组合数取模的枢纽。这一课没学扎实，后面刷题会到处碰壁。
2. 欧拉函数到底在数什么：定义、性质到单点计算
2.1 φ(n)的定义：从8和12这两个小例子入手
欧拉函数 φ(n) 的定义是：在 1 到 n 之间，有多少个整数与 n 互质。注意是“1到n”这个闭区间，n本身也算一个，只要它和自己互质。n=1时，1和1的最大公约数是1，所以约定 φ(1)=1，这个约定在竞赛里非常重要，别漏掉。
拿小数字练一练。φ(8)：1到8里和8互质的数有1、3、5、7，一共4个，所以 φ(8)=4。φ(12)：1到12里和12互质的数有1、5、7、11，一共4个，所以 φ(12)=4。注意这两个结果一样，但“为什么一样”完全不是重点，重点是你要能独立数出来。
很多初学者会问：为什么非要从1数到n，直接枚举不就行了？枚举当然可以，但n一旦到10^7、10^12，枚举就彻底没戏。我们需要一个不用枚举的计算方式。
2.2 计算式不是背出来的：n∏(1-1/p)的推导脉络
欧拉函数有一个经典计算式：把n质因数分解为 n = p1^a1 * p2^a2 * ... * pk^ak，那么 φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk)。
乍一看这个式子很奇怪：为什么“乘上一堆(1-1/p)”就得到互质个数？我建议你用容斥原理来理解，比死记硬背稳得多。
设 n 的质因子集合为 {p1, p2, ..., pk}。我们要数的是1到n中“不被任何pi整除”的数字个数。先看总数n，然后减掉被p1整除的 n/p1 个，被p2整除的 n/p2 个……但这样会把同时被p1和p2整除的数多减一次，所以还得加回来 n/(p1*p2)，以此类推。容斥展开的结果正好就是 n∏(1-1/pi)。每乘一个 (1-1/p)，可以粗略理解为“把上一步剩下数字中能被p整除的那部分滤掉”，但真正严谨的解释是容斥，你只要记住它是展开后的紧凑写法就行。
举个例子，φ(2024)，先分解质因数：2024 = 2^3 * 11 * 23。于是 φ(2024) = 2024 * (1/2) * (10/11) * (22/23) = 880。这个结果我后面还要用，所以先放在这里。
2.3 单个欧拉函数的O(√n)求法：代码和坑
如果你只需要求一个数的欧拉函数，直接用质因数分解的方式就行，复杂度 O(√n)。
long long phi(long long n) { long long res = n; for (long long p = 2; p * p <= n; ++p) { if (n % p == 0) { res = res / p * (p - 1); while (n % p == 0) n /= p; } } if (n > 1) res = res / n * (n - 1); return res; }这个代码有几个细节值得说。第一，res = res / p * (p - 1) 的顺序不要写成 res= (1 - 1.0/p)，浮点数会在整除场景下出莫名其妙的问题，也会丢精度。第二，循环结束后如果 n>1，说明剩下的是一个大于√n的质因子，必须再处理一次。第三，p * p <= n 这里 p 是 long long，如果是 int 且 n 到 10^9 以上，pp 可能溢出，所以用 long long 是基本功。
提示：单点求 φ(n) 的代码建议背到条件反射级别，因为后面很多题的第一步就是分解质因数得到一个模数的 φ 值。
3. 线性筛一次预处理1到n的所有φ值：代码和转移规则
3.1 为什么需要线性筛而不是单个分解
单个分解朴素且有效，但竞赛题经常不是只问你一个 φ(n)，而是给你一个 n=10^6 甚至 10^7，要求预处理出所有 φ(1)、φ(2)、……、φ(n)，然后配合前缀和使用。这种情况如果每个数都去分解一次，复杂度是 O(n√n)，直接原地超时。
埃氏筛思路可以做到接近线性：先初始化 phi[i]=i，然后从小到大枚举质数 p，把 p 的所有倍数 j 更新为 phi[j] = phi[j] / p * (p - 1)。这个做法复杂度是 O(n log log n)，原理就是基于计算式，在筛的过程中把每个质因子的贡献乘进去。代码短、好解释，但存在一个隐患：一个合数会被它的多个质因子重复更新多次，虽然总次数可控，但如果想追求真正的 O(n)，就得用欧拉筛。
我在教学时一般直接上欧拉筛，原因不是因为埃氏筛不够快，而是欧拉筛本身和质数筛、积性函数预处理绑定在一起，练会它相当于一鱼多吃。
3.2 欧拉筛的三条转移规则和“最小质因子”原则
欧拉筛的核心保证：每个合数只被它的最小质因子筛掉一次。在这个基础上，phi[i * primes[j]] 可以由 phi[i] 直接转移，一共分两种情况，加上初始情况，统共三条规则：
| 当前状态 | phi[i * primes[j]] | 理由 |
|---|---|---|
| i 本身是质数 | i - 1 | 质数与1到i-1的所有数互质 |
| primes[j] 能整除 i | phi[i] * primes[j] | 没有引入新质因子，乘积只变指数 |
| primes[j] 不能整除 i | phi[i] * (primes[j] - 1) | 新增一个质因子，多乘(1-1/p)即乘(p-1)/p，整体多乘(p-1) |
第三条其实是用积性函数的性质：当 gcd(a,b)=1 时 φ(ab)=φ(a)φ(b)，而 φ(primes[j])=primes[j]-1。第二条则要稍微想一下：如果 p 已经整除 i，那么 ip 和 i 的质因子集合完全相同，只是某个质因子的指数加了1。假设那个质因子就是 p，那么 φ(ip) = ip∏(1-1/q) = p * i∏(1-1/q) = p * φ(i)。这里直接把 p 乘上去就行。
关键是那个 break：一旦 i % primes[j] == 0，就立刻跳出内层循环，不要再继续乘更大的质因子。只有这样才能保证“最小质因子”原则成立，也就是每个合数只会被它自己最小的质因子访问一次。
3.3 完整代码与边界处理
#include <bits/stdc++.h> using namespace std; const int N = 1000005; int phi[N]; int primes[N], cnt; bool isComposite[N]; void initPhi(int n) { phi[1] = 1; for (int i = 2; i <= n; i++) { if (!isComposite[i]) { primes[++cnt] = i; phi[i] = i - 1; } for (int j = 1; j <= cnt && i * primes[j] <= n; j++) { int x = i * primes[j]; isComposite[x] = true; if (i % primes[j] == 0) { phi[x] = phi[i] * primes[j]; break; } else { phi[x] = phi[i] * (primes[j] - 1); } } } }边界上最容易翻车的点有两个。一个是在 initPhi 之前忘记赋 phi[1]=1，导致后面所有依赖 phi[i] 的转移在 i=2 时就已经错了。另一个是 i * primes[j] 可能超过 n，所以循环条件必须写清楚，并且用 int 存 i * primes[j] 时要注意 n 最大范围，1e7以内 int 足够，但如果 n 更大建议直接用 long long。
这个代码在竞赛里还有一个变体：把 phi 和最小质因子数组一起维护，可以在 O(n) 内完成大量数论预处理。我的建议是先把这段代码跑熟，再往上叠加更多功能。
4. 欧拉定理的证明直觉：缩系、费马小定理和同类问题
4.1 缩系：欧拉定理证明的真正主角
欧拉定理说的是：如果 gcd(a, m) = 1，那么 a^φ(m) ≡ 1 (mod m)。
很多人直接背结论，然后拿去用，我一开始也是这么干的。但后来带学生时发现，不理解证明的人很容易记错前提条件，尤其是把“a和m互质”这个条件丢掉。所以我建议至少把证明核心过一遍，哪怕只看个大意。
证明里的主角是“简化剩余系”，也叫缩系。所谓模m的缩系，就是从1到m中挑出所有与m互质的数，比如模8的缩系是{1,3,5,7}，模12的缩系是{1,5,7,11}。缩系的元素个数恰好是 φ(m)。
关键性质是：如果 r 遍历模m的缩系，且 gcd(a,m)=1，那么 a*r 取模m后得到的集合仍然是模m的缩系。换句话说，把整个缩系同时乘上一个与m互质的数，不会改变“哪些数与m互质”这件事的集合分布。
4.2 把证明走一遍：消去法的关键步骤
设模m的缩系为 r1, r2, ..., r_φ(m)。考虑它们的乘积 P = r1 * r2 * ... * r_φ(m)。
由于 ari 仍然构成一组缩系，所以 r1r2*...r_φ(m) ≡ (ar1)(ar2)...(a*r_φ(m)) (mod m)。右边整理一下，就是 a^φ(m) * P ≡ P (mod m)。
现在关键步骤来了：P = r1r2...*r_φ(m)，而每个ri都与m互质，所以P也与m互质。两个同余式两边都是P，因为P在模m下可逆，所以可以在等式两边同时消去P，得到 a^φ(m) ≡ 1 (mod m)。
这个“消去”就是逆元的雏形：只有与模数互质的数才有逆元，才能“两边除以它”。所以整个定理的成立，本质原因是底数和模数互质，导致乘法变换不会把缩系映射乱掉。
4.3 费马小定理是欧拉定理的平凡特例
如果 m = p 是一个质数，那么 φ(p) = p-1，欧拉定理就退化成 a^(p-1) ≡ 1 (mod p)，这就是费马小定理，条件是 gcd(a,p)=1，也就是 p 不整除 a。
很多教材把费马小定理和欧拉定理分开讲，但从数学上看，费马小定理只是欧拉定理在“模数为质数”这个特例下的特殊形式。我建议在脑子里把这两个定理划等号：费马小定理更快，欧拉定理更通用，当你发现模数不是质数时，就把费马小定理换成欧拉定理，本质上还是同一个思路。
举个例子直观感受一下。取 a=3, m=8，φ(8)=4，那么 3^4=81 ≡ 1 (mod 8)。再取 a=2, m=5，φ(5)=4，那么 2^4=16 ≡ 1 (mod 5)。这两个数都不大，可以手算验证，验证几次之后，你对“缩系乘一圈会回到自己”这个直觉会强很多。
5. 欧拉函数和欧拉定理在CSP-S考场上的三种打开方式
5.1 大指数取模的标准流程与手算示例
第一种用法是降指数。遇到形如 a^b mod m、b 很大的题，如果 gcd(a,m)=1，就把指数 b 对 φ(m) 取模，然后用快速幂计算：a^(b mod φ(m)) mod m。原因是 a^φ(m) ≡ 1，所以每 φ(m) 个 a 相乘就回到1，指数只需要保留除以φ(m)的余数。
让我把开头那道题算完：求 3^1000000000 mod 2024。第一步检查 gcd(3,2024)=1，没问题。第二步算 φ(2024)=880，前面已经算过。第三步把指数1000000000对880取模，1000000000 mod 880 = 520，因为880×1136363=999999440？让我核对一下：880×1136363 = 880×1,136,363 = 999,999,440，余数560。实际上1000000000 mod 880：880×1,136,363=999,999,440，余560。那么原式就等价于 3^560 mod 2024。剩下用快速幂跑一下就行，这里不手算最终结果，重点在于指数从10^9变成了三位数，复杂度立刻从不可能变成了可计算。
如果 b 是字符串形式的大数，也没关系，读入后边读边对 φ(m) 取模。这几乎是竞赛里的标准套路：指数很大时，先看 gcd，再对 φ(m) 取模，然后快速幂。
“指数取模”这个操作太常用了，我甚至会在赛前提醒学生：只要看到指数大于等于φ，就先取模。注意是对 φ(m) 取模，不是对 m 取模，这两者差了十万八千里。
5.2 用欧拉定理求逆元：给非质数模数留一条路
第二种用法是求逆元。模 m 意义下，a 的逆元是满足 a*x ≡ 1 (mod m) 的 x。如果 gcd(a,m)=1，那么欧拉定理告诉我们 a^φ(m) ≡ 1，所以 a * a^(φ(m)-1) ≡ 1，即 a 的逆元就是 a^(φ(m)-1) mod m。
当 m 是质数时，这就是大家熟悉的 a^(p-2)，因为 φ(p)=p-1。所以费马小定理求逆元其实是欧拉定理求逆元的特例。很多资料只讲 a^(p-2)，结果选手一遇到模数为合数就抓瞎。其实在同一套代码里，只需要把 p-2 换成 φ(m)-1，然后把 φ(m) 用单点计算求出来就行。
这里有个性能取舍：如果只有一两次求逆元，用欧拉定理快速算 a^(φ(m)-1) 完全可行；但如果要预处理1到n的所有逆元，线性递推是首选。不过那是另一节课的内容，这里先把原理打扎实。
5.3 扩展欧拉定理：先记住结论
第三种用法是扩展欧拉定理，专门处理“底数和模数不互质”的情况。竞赛题里经常出现 a^b mod m，其中 gcd(a,m)≠1，比如 a 是m的倍数，此时费马小定理、欧拉定理统统失效。扩展欧拉定理给出的结论是：当 b ≥ φ(m) 时，
a^b ≡ a^(b mod φ(m) + φ(m)) (mod m)。
这个结论的核心是：只要指数够大，即使不互质也能降幂，只是需要在取模后的指数上再加一个 φ(m)。为什么是加一个 φ(m) 而不是只保留余数，这就是扩展欧拉定理和普通欧拉定理最大的区别，细节涉及“指数足够大之后尾数周期”的性质，我建议放在下一课专门展开。现在你只需要知道有这么个工具，并且它和普通欧拉定理合在一起，基本覆盖了CSP-S里所有指数取模的题目。
我帮学生总结了这么一张对照表，做题时先对号入座：
| 情形 | 用什么 |
|---|---|
| 模数 p 是质数，求 a 的逆元 | a^(p-2) mod p |
| 模数 m 非质数，但 gcd(a,m)=1 | a^(φ(m)-1) mod m |
| 指数超大，且 gcd(a,m)=1 | 指数对 φ(m) 取模，再快速幂 |
| 指数超大，且 gcd(a,m)≠1 | 扩展欧拉定理，指数 b mod φ(m) + φ(m) |
6. 我陪学生刷题踩过的五个坑：从案发现场到检查习惯
6.1 坑一：无脑用费马小定理
这个坑我见得最多。题目给的模数明明是一个合数，比如 998244353 这种是质数没错，但 1000000007 也是质数，于是不少选手形成路径依赖，看到“求逆元”就直接写 a^(p-2)。一旦模数变成 2024、999999937（这个其实是质数，但很多选手并不验证），结果就彻底崩了。
我的建议是：开始动笔之前，先花三秒判断模数是否质数。如果不会判断，就用线性筛预处理出质数表，或者干脆直接用欧拉定理公式，避免费马小定理。多算一次 φ(m) 的复杂度是 O(√m)，对于 m ≤ 10^9 完全没问题，但能帮你避开无数个WA。
6.2 坑二：不检查互质就上欧拉定理
欧拉定理的前提是 gcd(a,m)=1。我见过一个学生写大指数取模，题目里 a=10，m=100000，他直接指数取模 φ(m)，结果答案和暴力对不上。我让他手写算 gcd(10,100000)=10，他才意识到问题。但那时已经过去一个小时的调试时间。
固定流程应该这样：先求 gcd(a,m)，如果等于1，走普通欧拉定理；如果不等于1，别硬用，看看指数是否大于 φ(m)，是的话用扩展欧拉定理。这个流程不需要思考，纯粹是条件反射，但能挡住至少一半的数论翻车。
6.3 坑三：筛法和快速幂里的溢出与初始化
第三个坑是代码层面的。线性筛里 i * primes[j] 可能超过 int 上限，但我见过有人图省事用 int 存，n = 10^7 没事，n = 10^8 直接溢出变负数，数组就越界了。另一个很隐蔽的问题是快速幂的 res = 1 % mod，当 mod = 1 时，res 应该等于 0 而不是 1，否则所有结果都会错。虽然竞赛里模数很少给1，但万一碰到，这一行就能省一次罚时。
再补一个坑：φ数组不初始化。phi[1] = 1 一定要写，不写的话线性筛第一轮就会问题倍增。同样的道理，质数数组 primes 要用计数器 cnt 维护，不要把它当成 STL vector 然后顺手 clear，写错位置就全乱了。
6.4 从案发现场到检查习惯
如果让我给一条最实在的赛时建议，那就是：把所有带 mod 的题目，在做完样例后都额外做三件事——检查底数是否和模数互质；检查指数是用 φ(m) 取模还是用 m 取模；检查快速幂里的乘法是否会溢出 long long。
第一件事判断互质可以用 gcd；第二件事只需要回头看一眼代码；第三件事在 a、b、mod 都可能到 10^9 时，乘法结果最高到 10^18，long long 能装下，但如果三个数都到 10^18 的量级，就必须用“龟速乘”或者 __int128。这个判断也很简单：如果模数本身到 10^12 以上，就把快速幂里的乘法和加法都换成防溢出写法。
最后说一个个人习惯：每次赛前集训，我都会让学生把欧拉函数和欧拉定理相关的模板题重新手写一遍，不是背代码，而是要求他们一边写一边说清楚每一步在干什么。这样做的好处是，考场上遇到变形题时，你不是在“回忆代码”，而是在“重建逻辑”。数论题的代码往往就那么十几行，真正值钱的是你判断该用哪个定理、该对谁取模的那三秒钟。
