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^k1 到 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) / 510 × 1 / 2 × 4 / 5由于整数除法舍去小数10/255×42020/54也没有问题。可换一个极端例子 n 3只有因子 3n * (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一类是边界问题比如 n1、n2 时数组越界另一类是递推公式写反了把乘 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)。更进阶一点求 ∑_{i1}^{n} gcd(i, n) 这类式子可以用枚举 gcd 的取值 d 来做只有当 gcd(i, n) d 时i/d 和 n/d 互质所以个数是 φ(n/d)。于是∑_{i1}^{n} gcd(i, n) ∑_{d|n} d × φ(n/d)。这个式子看起来简单但它把 gcd 计数问题转化成了枚举 n 的因子和查 φ 表的问题在很多题目里都能直接套。类似的还有 ∑_{i1}^{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)。每次打开电脑看到它就在脑子里快速过一遍“为什么有这个公式不互质的数怎么剔怎么在代码里实现”想通了就关掉想不通就翻博客。坚持下来这五个问题就成了条件反射。
求第k小元素与Top-K)
