数论在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本身也算一个只要它和自己互质。n1时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)浮点数会在整除场景下出莫名其妙的问题也会丢精度。第二循环结束后如果 n1说明剩下的是一个大于√n的质因子必须再处理一次。第三p * p n 这里 p 是 long long如果是 int 且 n 到 10^9 以上pp 可能溢出所以用 long long 是基本功。提示单点求 φ(n) 的代码建议背到条件反射级别因为后面很多题的第一步就是分解质因数得到一个模数的 φ 值。3. 线性筛一次预处理1到n的所有φ值代码和转移规则3.1 为什么需要线性筛而不是单个分解单个分解朴素且有效但竞赛题经常不是只问你一个 φ(n)而是给你一个 n10^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] 能整除 iphi[i] * primes[j]没有引入新质因子乘积只变指数primes[j] 不能整除 iphi[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] 的转移在 i2 时就已经错了。另一个是 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。很多教材把费马小定理和欧拉定理分开讲但从数学上看费马小定理只是欧拉定理在“模数为质数”这个特例下的特殊形式。我建议在脑子里把这两个定理划等号费马小定理更快欧拉定理更通用当你发现模数不是质数时就把费马小定理换成欧拉定理本质上还是同一个思路。举个例子直观感受一下。取 a3, m8φ(8)4那么 3^481 ≡ 1 (mod 8)。再取 a2, m5φ(5)4那么 2^416 ≡ 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×1136363999999440让我核对一下880×1136363 880×1,136,363 999,999,440余数560。实际上1000000000 mod 880880×1,136,363999,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)1a^(φ(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。我见过一个学生写大指数取模题目里 a10m100000他直接指数取模 φ(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^18long long 能装下但如果三个数都到 10^18 的量级就必须用“龟速乘”或者 __int128。这个判断也很简单如果模数本身到 10^12 以上就把快速幂里的乘法和加法都换成防溢出写法。最后说一个个人习惯每次赛前集训我都会让学生把欧拉函数和欧拉定理相关的模板题重新手写一遍不是背代码而是要求他们一边写一边说清楚每一步在干什么。这样做的好处是考场上遇到变形题时你不是在“回忆代码”而是在“重建逻辑”。数论题的代码往往就那么十几行真正值钱的是你判断该用哪个定理、该对谁取模的那三秒钟。