搞竞赛的同学应该都有这种感觉数论不像图论和数据结构那样“看得见摸得着”没有直观的树、图或者队列给你画出来但它在CSP-S提高组里的存在感却一点不低。今天这篇专题课我们专注解决两个互为表里的基础概念欧拉函数和欧拉定理。这是整个数论体系里最核心的地基后面要学的模逆元、同余方程、卢卡斯定理、甚至莫比乌斯反演全都要从这里长出来。文章只讲数学原理不掺水分适合正在备战CSP-S、对数论还处于“听过但不太会用”阶段的同学也适合想把原理补扎实的选手慢慢读、反复读。我会把“为什么这样定义”“公式怎么来的”“证明怎么想出来的”“做题时怎么用”串起来讲。你会发现数论没有想象中那么玄一旦把逻辑理顺它就是一套非常精致的工具。1. 先弄明白欧拉函数在数什么——别急着背公式1.1 欧拉函数的定义数一数谁跟n互质欧拉函数通常记作φ(n)读作phi(n)。它的定义很朴素对于正整数 nφ(n) 表示区间 [1, n] 中所有与 n 互质的整数的个数。这里的“互质”指两个数的最大公约数为 1记作 gcd(a, n) 1。注意细节φ(1) 1因为 1 与 1 互质而我们平时数“与 n 互质的数”时1 总是被算进去的因为 gcd(1, n) 1 恒成立。从定义出发先手算几个φ(2) 1因为 [1,2] 中与2互质的数只有1φ(3) 2因为1和2都与3互质φ(4) 2因为与4互质的是1和3φ(5) 41、2、3、4全与5互质φ(6) 2与6互质的只有1和5。细心的你会发现当 n 是质数 p 时φ(p) p-1因为 1 到 p-1 的所有正整数都与 p 互质唯独 p 自己不满足。这个观察后面会反复用到。理解了定义之后你可能会问一个很实际的问题竞赛里什么时候会让我“数互质个数”太多场景了。比如求分母为 n 的最简真分数数量本质就是 φ(n)某些计数题要求统计与某个数互质的排列数、方案数欧拉定理求逆元时需要先算 φ(m)一些数论求和题里φ(n) 作为函数被批量使用。所以它不只是个“定义”而是一把常用的钥匙。1.2 为什么CSP-S提高组绕不开数论你去翻最近几年的CSP-S真题会发现数论题几乎年年都有只是有时披着“组合计数”“递推优化”的皮。为什么命题人这么偏爱数论第一数论题的代码量往往不大但思维量极高。相比动辄上百行的高级数据结构一道好的数论题可能核心代码就二三十行考察的是你能不能看穿问题的数学本质。这在有限的考试时间里非常能拉开差距。第二数论是“模块化”的。欧拉函数、欧拉定理、逆元、中国剩余定理、卢卡斯定理……每个知识点之间衔接紧密一旦某个前置概念没弄懂后续所有内容都会像空中楼阁。很多选手学到后期卡壳回头一看往往是欧拉函数这里留下了隐患。第三数论与组合、概率、线性代数能自然交叉。比如组合数取模就必然涉及模逆元而模逆元最常见的推导工具就是欧拉定理。所以数论不是孤立的它是整个竞赛数学的血脉。因此把欧拉函数和欧拉定理这第一块基石夯实收益远超你的想象。2. 欧拉函数的计算与核心性质公式背后的逻辑2.1 从质因数分解看通项公式如果每次计算 φ(n) 都暴力枚举 1 到 n那复杂度是 O(n) 的n 一大就完全不可用。竞赛中我们需要一个高效公式。设 n 的质因数分解为n p₁^a₁ × p₂^a₂ × … × p_k^a_k那么欧拉函数的通项公式为φ(n) n × (1 - 1/p₁) × (1 - 1/p₂) × … × (1 - 1/p_k)用更“竞赛友好”的写法φ(n) n / p₁ × (p₁ - 1) / p₂ × (p₂ - 1) × … / p_k × (p_k - 1)注意质因数分解中每个不同的质因子只出现一次指数 a_i 不会出现在公式里。举两个例子。例1n 12 2² × 3φ(12) 12 × (1 - 1/2) × (1 - 1/3) 12 × 1/2 × 2/3 4。验证1到12中与12互质的是1、5、7、11正好4个。例2n 10 2 × 5φ(10) 10 × (1 - 1/2) × (1 - 1/5) 10 × 1/2 × 4/5 4。互质数1、3、7、9。那这个公式怎么理解呢本质是容斥原理。从1到n一共n个数先去掉所有 p₁ 的倍数再去掉 p₂ 的倍数……但由于有些数是 p₁ 和 p₂ 的公共倍数会重复去掉所以要加回来。一步一步推下来最后得到的就是这个连乘形式。简单说每一个质因子 p 相当于筛掉了“含 p 这个质因子的数”最后剩下的就是质因子与 n 完全不相交的数也就是互质数。提示代码实现时千万不要写成浮点运算n * (1 - 1.0 / p)会有精度隐患。正确写法是res res / p * (p - 1)先整除再乘全程都是整数运算。2.2 积性函数能把大数拆小算的关键欧拉函数最核心的代数性质是积性如果 gcd(a, b) 1则φ(a × b) φ(a) × φ(b)注意条件“互质”不能丢。比如 φ(2)1φ(4)2但 φ(2×4)φ(8)4不等于1×22原因就是 gcd(2,4)≠1。理解积性很重要。当你需要计算一个很大的 n 的欧拉函数时可以把它拆成互质因子的乘积分别计算再相乘。更常见的情况是在欧拉筛中批量求 φ(1) 到 φ(n)积性正是递推公式的根基。为什么积性成立把 a 和 b 的质因数分解写出来因为两者互质它们没有任何公共质因子。那么把通项公式展开φ(a) × φ(b) [a × ∏(1 - 1/p_i)] × [b × ∏(1 - 1/q_j)] (a×b) × ∏(1 - 1/r_t)其中 r_t 遍历 a×b 的所有不同质因子这恰好就是 φ(a×b)。证明结束。我建议你把上面这个过程在纸上完整推一遍推完就对“积性”不再只是记忆而是真正理解。2.3 因子求和恒等式一个容易被忽略的宝藏性质欧拉函数还有一个非常漂亮的性质它在很多计数题里会突然出现n Σ_{d | n} φ(d)也就是说把 n 的所有正因子的欧拉函数值加起来恰好等于 n 本身。验证一下n 6因子是1、2、3、6。φ(1)1φ(2)1φ(3)2φ(6)2加起来等于6成立。这个性质为什么对可以用约数分类来理解对每个 d | n统计 1 到 n 中满足 gcd(x, n) d 的数。令 x d × y那么 gcd(dy, n) d 等价于 gcd(y, n/d) 1且 1 ≤ y ≤ n/d。这样的 y 恰好有 φ(n/d) 个。所以n Σ_{d | n} φ(n/d) Σ_{d | n} φ(d)这一步交换了 d 与 n/d 的角色利用了约数的对称性。这个恒等式在竞赛里的用途主要有两个方向。一是反演入门它是莫比乌斯反演公式的思想雏形二是某些“求和”类题目需要你识别出“把 n 拆成它的因子欧拉函数和”这个操作来化简计算。我个人在刷题时发现很多选手对公式记得滚瓜烂熟但遇到 Σ_{d|n} φ(d) 这种结构就是想不起来等于 n。建议把这条恒等式连同证明一起记理解之后它就会变成你的“反射弧”看到一个因子求和第一反应就是它。3. 欧拉定理从理解到严格证明3.1 定理陈述与直觉理解欧拉定理的完整陈述如下设 m 是大于1的正整数a 是满足 gcd(a, m) 1 的整数则a^φ(m) ≡ 1 (mod m)如果你第一次见这个式子可能觉得突兀为什么随便一个与 m 互质的数它的 φ(m) 次方就同余于1了直观理解可以这样想模 m 的“互质剩余系”里一共有 φ(m) 个“合法”的数。用这个合法数去做循环置换恰好转一圈回到原点而 φ(m) 就是这圈的周期。欧拉定理本质上在说在模 m 的乘法世界里互质数的阶一定整除 φ(m)。举个例子m 7φ(7) 6。任取与7互质的数比如 a 22^1 2 ≡ 2 (mod 7)2^2 4 ≡ 4 (mod 7)2^3 8 ≡ 1 (mod 7)看到没其实 2^3 就已经等于1了但欧拉定理保证了 2^6 (2^3)^2 ≡ 1。也就是说 φ(7)6 不是最小周期但一定是周期的倍数。3.2 严格证明简化剩余系的一次置换欧拉定理的证明是整个数论里最优雅的证明之一它依赖一个关键工具——简化剩余系。设模 m 的一个简化剩余系为S {x₁, x₂, …, x_φ(m)}这里每个 x_i 与 m 互质且两两在模 m 意义下不同余。最常见的简化剩余系可以取 1 ≤ x m 且 gcd(x, m)1 的所有数。比如 m10 时S {1, 3, 7, 9}。现在固定一个满足 gcd(a, m) 1 的 a。我们来考察集合aS {ax₁, ax₂, …, ax_φ(m)}这里有三个关键论断第一每个 ax_i 与 m仍然互质。因为 gcd(ax_i, m) 1需要两个条件gcd(a, m)1 和 gcd(x_i, m)1两者都满足乘积自然也与 m 互质。第二这些数在模 m 下两两不同余。假设 ax_i ≡ ax_j (mod m)那么 m 整除 a(x_i - x_j)。由于 gcd(a, m) 1所以 m 必须整除 x_i - x_j。但 x_i 与 x_j 是简化剩余系里两个不同的数它们模 m 不同余差不可能被 m 整除。矛盾。第三数量正好是 φ(m) 个。既然两两不同余且都与 m 互质那么集合 {ax_i mod m} 和 S 其实就是同一个集合只是排列顺序不同。接下来是见证奇迹的时刻把所有元素乘起来。左边∏(ax_i) a^φ(m) × (x₁x₂…x_φ(m))右边∏x_i x₁x₂…x_φ(m)因为两个集合完全一致所以a^φ(m) × (x₁x₂…x_φ(m)) ≡ x₁x₂…x_φ(m) (mod m)最后一步设 P x₁x₂…x_φ(m)。由于每个 x_i 都与 m 互质所以 P 与 m 互质模 m 意义下可以约去。两边同除以 P得到a^φ(m) ≡ 1 (mod m)证毕。请你体会一下这个证明的精髓通过构造一个“置换”把 φ(m) 个元素乘在一起让未知的排列信息全部抵消只剩下 a^φ(m)。这种“让结构自己说话”的手法在数论证明里出现频率极高后面学原根、学二次剩余还会遇到。提示初学者最容易在最后一步“同除以 P”上较真。同余式中的除法不是随便做的只有当除数与被除的模数互质时才能两边同时约去。这里 P 与 m 互质所以是合法的。3.3 费马小定理特例同样能打当 m 是质数 p 时φ(p) p - 1欧拉定理退化成a^(p-1) ≡ 1 (mod p)其中 p 为质数p 不整除 a这就是费马小定理。很多教材把费马小定理单独拿出来讲但你要明白它只是欧拉定理的一个特例。记忆上可以合并一个互质数的“周期”要么是 φ(m)要么是它的因子当 m 是质数时周期必然整除 p-1。费马小定理最重要的竞赛应用是模质数逆元。对于质数 p 和 1 ≤ a pa^(p-1) ≡ 1 (mod p)两边同乘 a^(-1)即逆元可得a^(p-2) ≡ a^(-1) (mod p)也就是说a 的模 p 逆元等于 a^(p-2) 模 p。这个结论你会在组合数取模、概率期望、同余方程里反复用到。4. 欧拉函数与欧拉定理在CSP-S中的典型应用4.1 模逆元竞赛中的高频操作先解释什么是模逆元。若 gcd(a, m) 1称整数 x 为 a 在模 m 意义下的逆元如果满足a × x ≡ 1 (mod m)逆元的直观意义在模 m 的“运算圈”里x 就是 a 的倒数。有了逆元除法在模运算下就变得有意义了。怎么求逆元欧拉定理直接给出了一个通解由 a^φ(m) ≡ 1 (mod m)可得a × a^(φ(m) - 1) ≡ 1 (mod m)因此 a 的逆元就是a^(φ(m) - 1) mod m。当 m 是质数时就变成更熟悉的a^(m-2) mod m配合快速幂 O(log m) 求解。当 m 不是质数时先用欧拉函数求出 φ(m)再用快速幂计算 a^(φ(m)-1) % m前提仍是 gcd(a, m)1。这里要提醒一句如果 m 较小比如题目里的模数是固定的 1e97它其实就是个质数那直接用费马小定理最省事。只有当模数不保证是质数时才需要考虑扩展欧几里得或者其他方法。不过扩展欧几里得是另一讲的内容今天先不展开。4.2 大指数取模先降幂再快速幂竞赛中经常遇到“计算 a^b mod m其中 b 巨大”的问题。b 可能有 10^100 甚至更大根本无法直接算指数。当 gcd(a, m)1 时欧拉定理提供了一个非常优雅的降幂公式a^b ≡ a^(b mod φ(m)) (mod m)为什么成立设 b k × φ(m) r其中 r b mod φ(m)。那么a^b a^(k×φ(m)r) (a^φ(m))^k × a^r ≡ 1^k × a^r a^r (mod m)于是指数就可以先对 φ(m) 取模把“巨大指数”压缩到可以直接快速幂的范围内。看一个具体例子求 7^1000 mod 10。φ(10)4且 gcd(7,10)1。1000 mod 4 0所以 7^1000 ≡ 7^0 1 (mod 10)。验证一下7^17, 7^249≡9, 7^363≡3, 7^421≡1 (mod 10)周期是41000能被4整除结果确实是1。再来一个求 2^1000000000 mod 7。φ(7)61000000000 mod 6 4。2^4 16 ≡ 2 (mod 7)。这就是把 O(b) 的问题变成 O(log φ(m)) 的典型案例。注意这样降幂的前提是 gcd(a, m)1。如果两者不互质情况会更复杂通常会用到扩展欧拉定理当指数足够大时a^b ≡ a^(b mod φ(m) φ(m)) mod m。这部分属于进阶内容但你在做题前一定要检查互质条件否则容易白白丢分。4.3 C实现从单点计算到批量筛法掌握了原理代码就是水到渠成的事。先写单点求欧拉函数这个代码在所有讲解里几乎一致// 单点求欧拉函数 复杂度O(sqrt(n)) int phi(int n) { int ans n; for (int i 2; i * i n; i) { if (n % i 0) { ans ans / i * (i - 1); // 核心公式先除后乘防溢出 while (n % i 0) { n / i; // 除去所有该质因数 } } } if (n 1) { // 剩余一个大于sqrt的质因子 ans ans / n * (n - 1); } return ans; }这个代码的关键在于枚举 i 时一旦发现 n % i 0就说明 i 是一个新的质因子因为之前小的质因子都除光了。对每个质因子执行ans ans / i * (i - 1)再把 n 里所有 i 的幂全部除掉。最后如果 n 1说明 n 本身是一个大于根号原来的那个数的质因子也要处理。如果题目要求计算 [1, N] 所有数的欧拉函数单点计算的总复杂度是 O(N√N)在 N10^6 时明显不可行。这时候用质数筛法批量计算接近 O(N log log N)const int MAXN 1000000; int phi[MAXN 5]; void sievePhi(int n) { for (int i 1; i n; i) phi[i] i; for (int i 2; i n; i) { if (phi[i] i) { // 说明i是质数 for (int j i; j n; j i) { phi[j] phi[j] / i * (i - 1); } } } }原理很简单初始化 phi[i] i然后遍历每个质数 i将其所有倍数 j 套用公式“乘以 (1 - 1/i)”即phi[j] phi[j] / i * (i - 1)。这个筛法的时间复杂度大约 O(N log log N)在 N ≤ 10^7 时都能接受。更高阶的版本是线性筛可以在 O(N) 内同时求出质数表和欧拉函数主要用到了积性vectorint primes; int phi[MAXN]; bool vis[MAXN]; void linearPhi(int n) { phi[1] 1; for (int i 2; i n; i) { if (!vis[i]) { primes.push_back(i); phi[i] i - 1; // 质数的欧拉函数 } for (int p : primes) { if (1LL * i * p n) break; vis[i * p] true; if (i % p 0) { phi[i * p] phi[i] * p; // i含质因子p break; } else { phi[i * p] phi[i] * (p - 1); // 积性 } } } }建议初学者先把前两个版本练熟线性筛等理解了积性公式之后再来追。5. 初学者最容易踩的坑与我的实战建议5.1 三个高频错误附避免方法第一个错误忘记特判 n 1。φ(1)1但有些同学在写代码时如果循环因子从 1 开始或者把 ans 初始化为 n 后n1 时会直接返回1这没问题但很多推导性质时容易漏掉 n1 的特殊情况比如用“质因子个数”去理解就会觉得 φ(1) 应该是0完全不对。第二个错误筛法里用浮点运算。phi[j] phi[j] * (1 - 1.0 / i)在数大之后会出精度问题结果可能差1。正确做法永远是phi[j] phi[j] / i * (i - 1)先整除后乘。第三个错误欧拉定理降幂时不检查互质条件。遇到 a^b mod m一看指数大就直接 a^(b % phi(m))但如果 gcd(a,m) ≠ 1这步推导是不成立的。做题时先判断互质不互质就需要走扩展欧拉定理不要硬套。另外一个经常被忽略的小点快速幂底数要先取模。写代码时fpow(a, b, mod)内部第一行如果是long long res 1 % mod还好但如果直接把 a 放进去乘当 a 很大且没有先a % mod第一轮乘法就可能溢出 long long。养成习惯a % mod写在快速幂开头。5.2 刷题路线与实战策略理论学完得在题目里练才记得牢。我建议按这个顺序来先做纯欧拉函数计算题给定 n求 φ(n)。这种题主要是练代码模板确保单点计算和筛法模板都滚瓜烂熟。再做结合欧拉定理的题目比如给出 a、b、m求 a^b mod m且保证互质。这种题练的是“先降幂再快速幂”的复合思路。最后找一些盖上了“组合计数”外衣的题里面常常藏着逆元、费马小定理的应用。做的时候有意识地问自己这里有没有用到欧拉函数构造的简化剩余系有没有用逆元来消除模运算下的除法刷题时我有个习惯不要马上看题解先判断这题属于“数论”的哪个分支再想能不能用今天讲的原理转化问题。把每道题当成一次“原理应用训练”而非“代码训练”收获会大很多。再分享一个实战中省时间的小技巧如果题目模数是固定的质数比如 998244353、1000000007那逆元直接写fpow(x, mod - 2, mod)连 φ 都不用算。如果模数是合数就老老实实先筛出或算出 φ(m)再按公式走。在赛场上多花十秒钟判断模数类型能避免大量无效计算。
