带CSP-S提高组这几年我经常跟学生说数论这关你早过晚过都得过。不少同学一听到欧拉函数、欧拉定理就发怵觉得数学味太浓跟写代码没关系。但实际上这两个工具几乎年年出现在提高组的备考赛题里——要么直接当考点要么藏在快速幂、模逆元、指数化简这些高频操作后面。今天这篇专题课就是把欧拉函数和欧拉定理的数学原理彻底讲清楚顺带给出可以直接上手的C实现让你在CSP-S赛场上遇到相关题面时心里真正有底。这篇适合谁看你不需要任何数论基础只要会C的循环、数组、函数知道什么叫取模运算就能跟着走。如果你是刚学完质因数分解和快速幂正准备往提高组数论进阶的同学这一篇就是给你搭的台阶。我会先讲数学原理再给代码模板最后列考场上最容易踩的坑。原理部分最好自己动手推一遍别只看光看不练很难真正变成自己的东西。1. 数论在CSP-S中的地位先看清楚战场再上阵1.1 为什么提高组绕不开数论先说一个很多人问过的问题CSP-S提高组到底考不考数学答案是考而且是硬核地考。从近几年的题目看质数判定、质因数分解、最大公约数、同余方程、乘法逆元这些数论基础操作几乎是以标配身份出现的。哪怕是一道表面上与数论无关的题比如组合计数、字符串哈希、快速幂加速递推底层也全是模运算和同余结构。你要拿高分数论这块底盘得先夯实。数论好在它有边界知识点是固定的考法是有套路的。比起树上DP、毒瘤数据结构那些千变万化的题数论更偏向“你学得透彻分数就稳定”。欧拉函数和欧拉定理正是这个板块里的核心零件——前者是计数函数后者是同余世界的定理。搞懂它们之后再回头看逆元、降幂、互质计数这一类题你会看到完全不同的风景。1.2 欧拉函数会在什么题目里出现欧拉函数φ(n)在题目里出场通常有三种面貌。第一种是裸考察直接给你一个n要求计算与n互质且不超过n的数有多少个。这类送分题看似简单实际上考察的就是你会不会用分解质因数的公式去求φ(n)能不能处理好边界情况。第二种藏在取模化简里题目让算一个天大的指数表达式比如a^b mod mb大到连long long都塞不进。这时候欧拉定理就是你的降维武器——先把指数降下来再交给快速幂处理。第三种是计数类问题需要统计1到n里跟某个数互质的数的个数或者反过来统计不互质的。排列、圆桌、环排列这类组合题的方案数也常常要用φ(n)去重或做约束。明白这三类之后再学原理你就知道每个公式和性质到底是为了哪类题准备的学起来不迷茫也不会有“这东西学了有什么用”的疑问。2. 欧拉函数定义、公式、性质一次理清2.1 从“数个数”理解欧拉函数欧拉函数的定义一句话就能说清对于正整数nφ(n)表示从1到n之间与n互质的整数的个数。注意这里包含1因为gcd(1,n)1对任意正整数n都成立所以φ(1)1。我给学生讲课的时候喜欢把它翻译成“数座位”问题你有一排编号1到n的座位现在要数出哪些编号跟n没有公共质因子数出来的数量就是φ(n)。例如n6从1到6里跟6互质的有1和5两个所以φ(6)2。再看n12从1到12里跟12互质的只有1、5、7、11四个所以φ(12)4。为什么用“互质”这个条件而不是“不等于某个数”因为互质关系在乘法和模运算下性质特别好。两个互质的数相乘结果跟原来的数也保持互质关系不会被打乱。这正是后面欧拉定理成立的关键也是所有计数类推导的地基。2.2 计算通式是怎么来的真正的难点在公式。如果n分解质因数是n p1^k1 * p2^k2 * ... * pr^kr那么φ(n) n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pr)很多同学第一次看到这个式子都会问为什么是连乘不是连加我的建议是不要死记用容斥原理推一遍就记住了。以n12为例122^23。先把1到12所有数都看作候选人一共12个。第一步去掉2的倍数也就是12/26个剩下6个。第二步去掉3的倍数也就是12/34个但这里有个重复——既是2的倍数又是3的倍数的数也就是6的倍数被减了两次所以要加回来12/62个。于是剩余12 - 6 - 4 2 4个。你看正好是φ(12) 12(1-1/2)*(1-1/3) 4。扩展到多个质因子就是标准的容斥展开展开后恰好等价于连乘公式。所以记忆公式时你可以把它理解成“每个不同质因子按比例筛掉一部分”筛掉的比例是1/p剩下的就是1-1/p。这个“按比例筛”的直觉比死记公式有用得多。2.3 做题必须掌握的五个性质公式之外这五个性质我建议直接背考试中反复在用。性质1当p是质数时φ(p)p-1。因为1到p-1的每个数都与p互质直接数出来就是这些。性质2当p是质数、k≥1时φ(p^k)p^k - p^(k-1)。推导也很直观1到p^k里不互质的数就是能被p整除的数总共p^(k-1)个用总数减去即可。性质3欧拉函数是积性函数。如果gcd(a,b)1那么φ(a*b)φ(a)*φ(b)。这个性质是各种线性筛算法的数学依据一定要刻在脑子里后面写代码全靠它。性质4对于n2φ(n)一定是偶数。这个结论在有些题目里会用来排除选项或做奇偶分析虽然用得不算频繁但遇到时能省不少时间。性质5约数和恒等式。对n的所有约数d求φ(d)之和结果等于n。这个式子数学上很漂亮偶尔会在推导题里作为桥梁出现备赛阶段值得混个脸熟。3. 欧拉定理费马小定理之后的那一步3.1 费马小定理是特例说到欧拉定理得先带出费马小定理。费马小定理说的是如果p是质数且a不是p的倍数那么a^(p-1) ≡ 1 (mod p)。比如p7a33^6729729除以7余1验证无误。这个定理在质数模数下非常有用但竞赛里模数不一定都是质数。比如模数是12、15或者像常见的998244353这样的数时费马小定理就不一定适用了。欧拉定理就是费马小定理的推广把“质数p”放宽成“任意正整数n”对应的指数也从p-1换成了φ(n)。先把这个关系理清你就能记住一个关键判断模数是质数用费马小定理模数是任意数看欧拉定理。3.2 欧拉定理的严格证明欧拉定理的标准形式是如果gcd(a,n)1那么a^φ(n) ≡ 1 (mod n)。证明思路不复杂但每一步都有讲究。我们取模n意义下的一个简化剩余系也就是一组数r1, r2, ..., rk其中kφ(n)这组数里任意两个模n不同余而且每个数都与n互质。比如n12φ(12)4一组简化剩余系是{1,5,7,11}。接着把每个ri都乘以a得到ar1, ar2, ..., ark。关键点来了因为gcd(a,n)1乘a之后这些数仍然都与n互质。同时它们模n之后也仍然两两不同余——如果ari ≡ a*rj (mod n)因为a在模n下可逆就能推出ri ≡ rj (mod n)与假设矛盾。所以在模n意义下这组新数依然是一组完整的简化剩余系。于是整组数连乘模n应该和原来那组数连乘模n同余(a^φ(n)) * (r1r2...rk) ≡ r1r2*...*rk (mod n)由于每个ri都与n互质它们的乘积也与n互质两边可以约掉这个乘积最终得到a^φ(n) ≡ 1 (mod n)。证明完毕。3.3 降幂欧拉定理最常见的两种用法欧拉定理在代码题里最直接的用途是降幂。当gcd(a,n)1时指数b如果是天文数字直接用a^b mod n可能根本算不动但可以先把b对φ(n)取模a^b ≡ a^(b mod φ(n)) (mod n)原理就是设b q*φ(n) r那么a^b (a^φ(n))^q * a^r ≡ 1^q * a^r a^r (mod n)。这一步放在快速幂之前能瞬间把指数从10^18级别压到1e7级别运算量天差地别。第二种常见用法是求逆元。当gcd(a,n)1时a的逆元就是a^(φ(n)-1) mod n因为a * a^(φ(n)-1) a^φ(n) ≡ 1 (mod n)。在模数不是质数、费马小定理没法用的时候这条路是通用的。当然实际比赛中我更推荐先用扩展欧几里得求逆元因为它不需要算φ(n)又快又稳但欧拉定理这条路你必须会因为某些题里求逆元只是顺带操作φ(n)已经算好了直接用这个公式反而省事。4. C实现从单个数求解到线性筛4.1 单个数求欧拉函数分解质因数法单个n的欧拉函数最稳的写法就是按公式分解质因数复杂度O(√n)对1e9以内的n都够用。int phi(int n) { int res n; for (int i 2; 1LL * i * i n; i) { if (n % i 0) { res res / i * (i - 1); while (n % i 0) n / i; } } if (n 1) res res / n * (n - 1); return res; }这里有三个细节值得单独说。第一res初始化为n每找到一个质因子i就执行res res / i * (i - 1)本质上就是在乘(1-1/i)。用整数除法运算避免引入浮点误差。第二循环里先除后乘能防止中间溢出。res / i * (i - 1)是先除以较大的i再乘以较小的i-1只要res本身没超出int上限这一步就是安全的。如果你写成res * (i - 1) / in比较大的时候中间结果可能直接爆掉毫无必要地给自己挖坑。第三循环结束后如果n还大于1说明原数中剩下一个大于根号n的质因子必须补上这一项。这个坑很多新手都会踩——只处理循环内的情况漏掉最后一个大质因子算出来的φ值凭空少乘一项。比如n2*999983循环在i2时处理完2剩余n999983是一个大于根号的大质数最后一步不写的话结果完全错误。4.2 线性筛求解1..n的所有欧拉函数如果题目要求多次查询不同位置的欧拉函数值或者需要1到n所有数的φ值单个数分解就不够快了。这时用线性筛预处理可以把总复杂度压到O(n)而且代码量并不大。线性筛名字里带“线性”是因为每个合数只会被它的最小质因子筛掉一次。筛的过程顺便维护phi数组核心逻辑只有两条分支当i能被当前质数p整除时说明p是i的最小质因子此时phi[ip] phi[i] * p否则phi[ip] phi[i] * (p-1)。下面这份代码我实测过写法上做了一些工程化处理更顺手。const int MAXN 1000000; int phi[MAXN 1]; vectorint primes; bool isComp[MAXN 1]; void init_phi(int n) { phi[1] 1; for (int i 2; i n; i) { if (!isComp[i]) { primes.push_back(i); phi[i] i - 1; } for (int p : primes) { long long v 1LL * i * p; if (v n) break; isComp[v] true; if (i % p 0) { phi[v] phi[i] * p; break; } else { phi[v] phi[i] * (p - 1); } } } }为什么两条公式长这样从定义推。假设n i * pp是质数。如果p能整除i那么n的所有质因子集合跟i一样只是p的指数多了1。代入公式会发现φ的值变成φ(i)*p。如果p不能整除i那么gcd(i,p)1由积性性质直接得φ(n)φ(i)φ(p)φ(i)(p-1)。逻辑对应的正是代码里的if和else分支。注意break的含义。内层循环遇到i % p 0时就必须停因为后面的质数都比p大不可能再是i的最小质因子。继续筛下去会让每个合数被多次标记线性性质就破坏了复杂度退化phi数组也可能被覆盖成错误值。这段代码值得你亲手敲一遍敲完再对照注释看两遍印象会深很多。4.3 实现中的易错点清单线性筛的易错点我按出现频率排个序。第一数组越界。MAXN必须比需要的n大1因为你要用phi[n]。如果查询下标是1到n数组至少开MAXN1很多人开小了直接RE。建议养成习惯所有预处理数组统一开成MAXN1。第二break写错位置。线性筛的break必须在i % p 0的分支里一旦漏掉筛法退化重复标记会拖慢速度而且phi数组可能被多次赋值某些值最后变成错的而你根本察觉不到。第三溢出问题。i * p在极端情况下超过int范围所以要么用long long接收要么写成if (i n / p) break。两种写法都安全我用的是long long版的v变量顺手也解决了后续判断。第四phi[1]的初始化。这个最容易忽略。有人写线性筛时从i1开始枚举或者忘了给phi[1]赋值导致后续查询phi[1]返回垃圾值。记住phi[1]1这是定义的一部分不需要额外推导。第五多组数据时不要重复调用init_phi。预处理数组做一次就够了重复调用不会让结果变更正确反而浪费时间。如果你写的函数里还做了清空操作那就更亏了。5. 应用与备考把数学原理变成考场上的能力5.1 三种高频应用场景先看第一类大指数取模。题目给你底数a、指数b和模数mb可能以十进制字符串的形式给出长到几百位。传统做法根本没法读入成一个整数但你可以把字符串从头到尾读一遍边读边对φ(m)取模把b变成b mod φ(m)然后快速幂。只要gcd(a,m)1这一步就是合法的。这种题在提高组里不算罕见从字符串取模到欧拉定理的应用是一整套固定流程。第二类乘法逆元。模数m是质数时费马小定理直接给出逆元a^(m-2)模数不是质数时只要gcd(a,m)1欧拉定理推出逆元是a^(φ(m)-1)。虽然复杂度比扩展欧几里得求逆元高一点但在某些题目里φ(m)已经被预处理好了用欧拉定理公式反而少写一次扩展欧几里得的调用。第三类是互质计数问题。比如问1到n里有多少个数与m互质如果m是质数答案是n - n/m简单如果m是合数就得用容斥原理或者预处理好的phi数组。这种计数题在组合数学大题里经常藏在中间步骤不会专门告诉你“请用欧拉函数”但你看穿了它就是送分题看不穿就可能卡住。5.2 常见问题与排查速查表我整理了平时学生问得最多的几个问题直接做成速查表现象可能原因怎么处理算出来的φ(n)为0循环里把n约成了1最后还无条件除了一次只在最后if(n1)时再补除别无条件除模数很大但结果溢出快速幂里乘法没取模所有中间结果用long long并逐次取模线性筛少了某些phi值break分支写错或边界判断遗漏检查i%p0时是否break以及内层循环的越界条件大指数降幂结果不对忽略了gcd(a,m)1的情况基础欧拉定理只满足互质条件否则要用扩展欧拉定理后面专题再讲时间超限单个n反复分解质因数改用init_phi做预处理这张表不能覆盖所有情况但确实解决了我在训练中见过的八成问题。真去排查的时候先确认gcd和模运算的合法性再检查边界和初始化通常比盲调代码快得多。尤其是“gcd(a,m)1”这个条件很多同学第一次做降幂题时根本没检查结果小数据乱对、大数据报错排查半天才发现是条件没满足。5.3 给备考同学的路线建议最后给一条实操路线按这个顺序学不容易乱。第一步动手把φ(n)的容斥推导自己重新写一遍再验证几组数φ(10)、φ(24)、φ(30)、φ(97)。算错了也不要紧关键是建立“按比例筛”的直觉顺便熟练分解质因数的过程。第二步自己默写单数分解法和线性筛两份模板。注意我说的是默写不是抄。只有脱离参考代码能写出来考试时才稳。默写之后把代码跑一遍用φ(1)1、φ(p)p-1、φ(p^k)p^k-p^(k-1)这些性质去验证输出能自查说明你真的理解了。第三步做三到五道结合欧拉定理的取模化简题每道题都先判断gcd(a,m)1是否成立再决定能不能用基础欧拉定理。这个判断动作要变成肌肉记忆。第四步把逆元和快速幂的模板串在一起练一遍因为欧拉定理的最终落脚点往往是快速幂调用。练熟了你会发现数论题之间其实是联动的并不是一个知识点一个知识点孤立存在。最后说点带训时的经验每年都有学生问我欧拉定理到底要不要证明我的答案始终是——你至少亲手推一遍哪怕推完就忘也比只背结论强得多。因为推导过程会强迫你理解“同余”“剩余系”“互质性”这些概念的真正含义而它们的组合能力正是数论题里最值钱的部分。很多同学上午刚背完结论下午做题还是不会用差别就在这。再分享一个小技巧写代码前先把要用的数学式子写在注释里。比如在phi函数上方写上φ(n) n*∏(1-1/p)在降幂代码旁边写上“gcd(a,m)1指数对φ(m)取模”。这个习惯成本极低但能让你在考场上一眼看出自己准备做哪一步紧张时不容易乱。希望这节专题课能成为你CSP-S数论路上的第一块稳定地基原理吃透了代码是水到渠成的事。 CSP-S数论必备：欧拉函数与欧拉定理详解及C++实现
带CSP-S提高组这几年我经常跟学生说数论这关你早过晚过都得过。不少同学一听到欧拉函数、欧拉定理就发怵觉得数学味太浓跟写代码没关系。但实际上这两个工具几乎年年出现在提高组的备考赛题里——要么直接当考点要么藏在快速幂、模逆元、指数化简这些高频操作后面。今天这篇专题课就是把欧拉函数和欧拉定理的数学原理彻底讲清楚顺带给出可以直接上手的C实现让你在CSP-S赛场上遇到相关题面时心里真正有底。这篇适合谁看你不需要任何数论基础只要会C的循环、数组、函数知道什么叫取模运算就能跟着走。如果你是刚学完质因数分解和快速幂正准备往提高组数论进阶的同学这一篇就是给你搭的台阶。我会先讲数学原理再给代码模板最后列考场上最容易踩的坑。原理部分最好自己动手推一遍别只看光看不练很难真正变成自己的东西。1. 数论在CSP-S中的地位先看清楚战场再上阵1.1 为什么提高组绕不开数论先说一个很多人问过的问题CSP-S提高组到底考不考数学答案是考而且是硬核地考。从近几年的题目看质数判定、质因数分解、最大公约数、同余方程、乘法逆元这些数论基础操作几乎是以标配身份出现的。哪怕是一道表面上与数论无关的题比如组合计数、字符串哈希、快速幂加速递推底层也全是模运算和同余结构。你要拿高分数论这块底盘得先夯实。数论好在它有边界知识点是固定的考法是有套路的。比起树上DP、毒瘤数据结构那些千变万化的题数论更偏向“你学得透彻分数就稳定”。欧拉函数和欧拉定理正是这个板块里的核心零件——前者是计数函数后者是同余世界的定理。搞懂它们之后再回头看逆元、降幂、互质计数这一类题你会看到完全不同的风景。1.2 欧拉函数会在什么题目里出现欧拉函数φ(n)在题目里出场通常有三种面貌。第一种是裸考察直接给你一个n要求计算与n互质且不超过n的数有多少个。这类送分题看似简单实际上考察的就是你会不会用分解质因数的公式去求φ(n)能不能处理好边界情况。第二种藏在取模化简里题目让算一个天大的指数表达式比如a^b mod mb大到连long long都塞不进。这时候欧拉定理就是你的降维武器——先把指数降下来再交给快速幂处理。第三种是计数类问题需要统计1到n里跟某个数互质的数的个数或者反过来统计不互质的。排列、圆桌、环排列这类组合题的方案数也常常要用φ(n)去重或做约束。明白这三类之后再学原理你就知道每个公式和性质到底是为了哪类题准备的学起来不迷茫也不会有“这东西学了有什么用”的疑问。2. 欧拉函数定义、公式、性质一次理清2.1 从“数个数”理解欧拉函数欧拉函数的定义一句话就能说清对于正整数nφ(n)表示从1到n之间与n互质的整数的个数。注意这里包含1因为gcd(1,n)1对任意正整数n都成立所以φ(1)1。我给学生讲课的时候喜欢把它翻译成“数座位”问题你有一排编号1到n的座位现在要数出哪些编号跟n没有公共质因子数出来的数量就是φ(n)。例如n6从1到6里跟6互质的有1和5两个所以φ(6)2。再看n12从1到12里跟12互质的只有1、5、7、11四个所以φ(12)4。为什么用“互质”这个条件而不是“不等于某个数”因为互质关系在乘法和模运算下性质特别好。两个互质的数相乘结果跟原来的数也保持互质关系不会被打乱。这正是后面欧拉定理成立的关键也是所有计数类推导的地基。2.2 计算通式是怎么来的真正的难点在公式。如果n分解质因数是n p1^k1 * p2^k2 * ... * pr^kr那么φ(n) n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pr)很多同学第一次看到这个式子都会问为什么是连乘不是连加我的建议是不要死记用容斥原理推一遍就记住了。以n12为例122^23。先把1到12所有数都看作候选人一共12个。第一步去掉2的倍数也就是12/26个剩下6个。第二步去掉3的倍数也就是12/34个但这里有个重复——既是2的倍数又是3的倍数的数也就是6的倍数被减了两次所以要加回来12/62个。于是剩余12 - 6 - 4 2 4个。你看正好是φ(12) 12(1-1/2)*(1-1/3) 4。扩展到多个质因子就是标准的容斥展开展开后恰好等价于连乘公式。所以记忆公式时你可以把它理解成“每个不同质因子按比例筛掉一部分”筛掉的比例是1/p剩下的就是1-1/p。这个“按比例筛”的直觉比死记公式有用得多。2.3 做题必须掌握的五个性质公式之外这五个性质我建议直接背考试中反复在用。性质1当p是质数时φ(p)p-1。因为1到p-1的每个数都与p互质直接数出来就是这些。性质2当p是质数、k≥1时φ(p^k)p^k - p^(k-1)。推导也很直观1到p^k里不互质的数就是能被p整除的数总共p^(k-1)个用总数减去即可。性质3欧拉函数是积性函数。如果gcd(a,b)1那么φ(a*b)φ(a)*φ(b)。这个性质是各种线性筛算法的数学依据一定要刻在脑子里后面写代码全靠它。性质4对于n2φ(n)一定是偶数。这个结论在有些题目里会用来排除选项或做奇偶分析虽然用得不算频繁但遇到时能省不少时间。性质5约数和恒等式。对n的所有约数d求φ(d)之和结果等于n。这个式子数学上很漂亮偶尔会在推导题里作为桥梁出现备赛阶段值得混个脸熟。3. 欧拉定理费马小定理之后的那一步3.1 费马小定理是特例说到欧拉定理得先带出费马小定理。费马小定理说的是如果p是质数且a不是p的倍数那么a^(p-1) ≡ 1 (mod p)。比如p7a33^6729729除以7余1验证无误。这个定理在质数模数下非常有用但竞赛里模数不一定都是质数。比如模数是12、15或者像常见的998244353这样的数时费马小定理就不一定适用了。欧拉定理就是费马小定理的推广把“质数p”放宽成“任意正整数n”对应的指数也从p-1换成了φ(n)。先把这个关系理清你就能记住一个关键判断模数是质数用费马小定理模数是任意数看欧拉定理。3.2 欧拉定理的严格证明欧拉定理的标准形式是如果gcd(a,n)1那么a^φ(n) ≡ 1 (mod n)。证明思路不复杂但每一步都有讲究。我们取模n意义下的一个简化剩余系也就是一组数r1, r2, ..., rk其中kφ(n)这组数里任意两个模n不同余而且每个数都与n互质。比如n12φ(12)4一组简化剩余系是{1,5,7,11}。接着把每个ri都乘以a得到ar1, ar2, ..., ark。关键点来了因为gcd(a,n)1乘a之后这些数仍然都与n互质。同时它们模n之后也仍然两两不同余——如果ari ≡ a*rj (mod n)因为a在模n下可逆就能推出ri ≡ rj (mod n)与假设矛盾。所以在模n意义下这组新数依然是一组完整的简化剩余系。于是整组数连乘模n应该和原来那组数连乘模n同余(a^φ(n)) * (r1r2...rk) ≡ r1r2*...*rk (mod n)由于每个ri都与n互质它们的乘积也与n互质两边可以约掉这个乘积最终得到a^φ(n) ≡ 1 (mod n)。证明完毕。3.3 降幂欧拉定理最常见的两种用法欧拉定理在代码题里最直接的用途是降幂。当gcd(a,n)1时指数b如果是天文数字直接用a^b mod n可能根本算不动但可以先把b对φ(n)取模a^b ≡ a^(b mod φ(n)) (mod n)原理就是设b q*φ(n) r那么a^b (a^φ(n))^q * a^r ≡ 1^q * a^r a^r (mod n)。这一步放在快速幂之前能瞬间把指数从10^18级别压到1e7级别运算量天差地别。第二种常见用法是求逆元。当gcd(a,n)1时a的逆元就是a^(φ(n)-1) mod n因为a * a^(φ(n)-1) a^φ(n) ≡ 1 (mod n)。在模数不是质数、费马小定理没法用的时候这条路是通用的。当然实际比赛中我更推荐先用扩展欧几里得求逆元因为它不需要算φ(n)又快又稳但欧拉定理这条路你必须会因为某些题里求逆元只是顺带操作φ(n)已经算好了直接用这个公式反而省事。4. C实现从单个数求解到线性筛4.1 单个数求欧拉函数分解质因数法单个n的欧拉函数最稳的写法就是按公式分解质因数复杂度O(√n)对1e9以内的n都够用。int phi(int n) { int res n; for (int i 2; 1LL * i * i n; i) { if (n % i 0) { res res / i * (i - 1); while (n % i 0) n / i; } } if (n 1) res res / n * (n - 1); return res; }这里有三个细节值得单独说。第一res初始化为n每找到一个质因子i就执行res res / i * (i - 1)本质上就是在乘(1-1/i)。用整数除法运算避免引入浮点误差。第二循环里先除后乘能防止中间溢出。res / i * (i - 1)是先除以较大的i再乘以较小的i-1只要res本身没超出int上限这一步就是安全的。如果你写成res * (i - 1) / in比较大的时候中间结果可能直接爆掉毫无必要地给自己挖坑。第三循环结束后如果n还大于1说明原数中剩下一个大于根号n的质因子必须补上这一项。这个坑很多新手都会踩——只处理循环内的情况漏掉最后一个大质因子算出来的φ值凭空少乘一项。比如n2*999983循环在i2时处理完2剩余n999983是一个大于根号的大质数最后一步不写的话结果完全错误。4.2 线性筛求解1..n的所有欧拉函数如果题目要求多次查询不同位置的欧拉函数值或者需要1到n所有数的φ值单个数分解就不够快了。这时用线性筛预处理可以把总复杂度压到O(n)而且代码量并不大。线性筛名字里带“线性”是因为每个合数只会被它的最小质因子筛掉一次。筛的过程顺便维护phi数组核心逻辑只有两条分支当i能被当前质数p整除时说明p是i的最小质因子此时phi[ip] phi[i] * p否则phi[ip] phi[i] * (p-1)。下面这份代码我实测过写法上做了一些工程化处理更顺手。const int MAXN 1000000; int phi[MAXN 1]; vectorint primes; bool isComp[MAXN 1]; void init_phi(int n) { phi[1] 1; for (int i 2; i n; i) { if (!isComp[i]) { primes.push_back(i); phi[i] i - 1; } for (int p : primes) { long long v 1LL * i * p; if (v n) break; isComp[v] true; if (i % p 0) { phi[v] phi[i] * p; break; } else { phi[v] phi[i] * (p - 1); } } } }为什么两条公式长这样从定义推。假设n i * pp是质数。如果p能整除i那么n的所有质因子集合跟i一样只是p的指数多了1。代入公式会发现φ的值变成φ(i)*p。如果p不能整除i那么gcd(i,p)1由积性性质直接得φ(n)φ(i)φ(p)φ(i)(p-1)。逻辑对应的正是代码里的if和else分支。注意break的含义。内层循环遇到i % p 0时就必须停因为后面的质数都比p大不可能再是i的最小质因子。继续筛下去会让每个合数被多次标记线性性质就破坏了复杂度退化phi数组也可能被覆盖成错误值。这段代码值得你亲手敲一遍敲完再对照注释看两遍印象会深很多。4.3 实现中的易错点清单线性筛的易错点我按出现频率排个序。第一数组越界。MAXN必须比需要的n大1因为你要用phi[n]。如果查询下标是1到n数组至少开MAXN1很多人开小了直接RE。建议养成习惯所有预处理数组统一开成MAXN1。第二break写错位置。线性筛的break必须在i % p 0的分支里一旦漏掉筛法退化重复标记会拖慢速度而且phi数组可能被多次赋值某些值最后变成错的而你根本察觉不到。第三溢出问题。i * p在极端情况下超过int范围所以要么用long long接收要么写成if (i n / p) break。两种写法都安全我用的是long long版的v变量顺手也解决了后续判断。第四phi[1]的初始化。这个最容易忽略。有人写线性筛时从i1开始枚举或者忘了给phi[1]赋值导致后续查询phi[1]返回垃圾值。记住phi[1]1这是定义的一部分不需要额外推导。第五多组数据时不要重复调用init_phi。预处理数组做一次就够了重复调用不会让结果变更正确反而浪费时间。如果你写的函数里还做了清空操作那就更亏了。5. 应用与备考把数学原理变成考场上的能力5.1 三种高频应用场景先看第一类大指数取模。题目给你底数a、指数b和模数mb可能以十进制字符串的形式给出长到几百位。传统做法根本没法读入成一个整数但你可以把字符串从头到尾读一遍边读边对φ(m)取模把b变成b mod φ(m)然后快速幂。只要gcd(a,m)1这一步就是合法的。这种题在提高组里不算罕见从字符串取模到欧拉定理的应用是一整套固定流程。第二类乘法逆元。模数m是质数时费马小定理直接给出逆元a^(m-2)模数不是质数时只要gcd(a,m)1欧拉定理推出逆元是a^(φ(m)-1)。虽然复杂度比扩展欧几里得求逆元高一点但在某些题目里φ(m)已经被预处理好了用欧拉定理公式反而少写一次扩展欧几里得的调用。第三类是互质计数问题。比如问1到n里有多少个数与m互质如果m是质数答案是n - n/m简单如果m是合数就得用容斥原理或者预处理好的phi数组。这种计数题在组合数学大题里经常藏在中间步骤不会专门告诉你“请用欧拉函数”但你看穿了它就是送分题看不穿就可能卡住。5.2 常见问题与排查速查表我整理了平时学生问得最多的几个问题直接做成速查表现象可能原因怎么处理算出来的φ(n)为0循环里把n约成了1最后还无条件除了一次只在最后if(n1)时再补除别无条件除模数很大但结果溢出快速幂里乘法没取模所有中间结果用long long并逐次取模线性筛少了某些phi值break分支写错或边界判断遗漏检查i%p0时是否break以及内层循环的越界条件大指数降幂结果不对忽略了gcd(a,m)1的情况基础欧拉定理只满足互质条件否则要用扩展欧拉定理后面专题再讲时间超限单个n反复分解质因数改用init_phi做预处理这张表不能覆盖所有情况但确实解决了我在训练中见过的八成问题。真去排查的时候先确认gcd和模运算的合法性再检查边界和初始化通常比盲调代码快得多。尤其是“gcd(a,m)1”这个条件很多同学第一次做降幂题时根本没检查结果小数据乱对、大数据报错排查半天才发现是条件没满足。5.3 给备考同学的路线建议最后给一条实操路线按这个顺序学不容易乱。第一步动手把φ(n)的容斥推导自己重新写一遍再验证几组数φ(10)、φ(24)、φ(30)、φ(97)。算错了也不要紧关键是建立“按比例筛”的直觉顺便熟练分解质因数的过程。第二步自己默写单数分解法和线性筛两份模板。注意我说的是默写不是抄。只有脱离参考代码能写出来考试时才稳。默写之后把代码跑一遍用φ(1)1、φ(p)p-1、φ(p^k)p^k-p^(k-1)这些性质去验证输出能自查说明你真的理解了。第三步做三到五道结合欧拉定理的取模化简题每道题都先判断gcd(a,m)1是否成立再决定能不能用基础欧拉定理。这个判断动作要变成肌肉记忆。第四步把逆元和快速幂的模板串在一起练一遍因为欧拉定理的最终落脚点往往是快速幂调用。练熟了你会发现数论题之间其实是联动的并不是一个知识点一个知识点孤立存在。最后说点带训时的经验每年都有学生问我欧拉定理到底要不要证明我的答案始终是——你至少亲手推一遍哪怕推完就忘也比只背结论强得多。因为推导过程会强迫你理解“同余”“剩余系”“互质性”这些概念的真正含义而它们的组合能力正是数论题里最值钱的部分。很多同学上午刚背完结论下午做题还是不会用差别就在这。再分享一个小技巧写代码前先把要用的数学式子写在注释里。比如在phi函数上方写上φ(n) n*∏(1-1/p)在降幂代码旁边写上“gcd(a,m)1指数对φ(m)取模”。这个习惯成本极低但能让你在考场上一眼看出自己准备做哪一步紧张时不容易乱。希望这节专题课能成为你CSP-S数论路上的第一块稳定地基原理吃透了代码是水到渠成的事。