文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载欧拉函数Eulers totient function$\phi(n)$ 是数论与算法竞赛中最重要的积性函数之一用于统计小于等于 $n$ 且与 $n$ 互素的整数个数。本文以 cp-algorithms 仓库的 phi-function.md 为骨架系统讲解其定义、五大核心性质、单点 $O(\sqrt n)$ 计算、$1 \sim n$ 的 $O(n\log\log n)$ 批量筛法、区间 $[L,R]$ 分段筛法并延伸到欧拉定理、费马小定理、幂次化简与非互素情形的推广公式。读完本文你将掌握 $\phi(n)$ 的完整计算工具箱并能在模逆元、原根、Burnside 引理等实战场景中熟练调用它。定义与基础取值欧拉函数 $\phi(n)$ 统计满足 $1 \le x \le n$ 且 $\gcd(x, n) 1$ 的整数 $x$ 的个数约定 $1$ 与任何整数互素。$n 1$ 时$\phi(1) 1$。前 21 个正整数的 $\phi(n)$ 取值如下n123456789101112131415161718192021φ(n)11224264641041268816618812从表中可以直观验证几个基本事实素数的 φ 值等于自身减一如 $\phi(7)6$而 $12 2^2 \times 3$ 这类合数的 φ 值明显小于 $n-1$因为与它不互素的数更多。核心性质计算 $\phi(n)$ 的理论基础以下四条性质足以让我们对任意正整数 $n$ 计算 $\phi(n)$性质 1素数。若 $p$ 为素数则对所有 $1 \le q p$ 都有 $\gcd(p, q) 1$于是$$\phi (p) p - 1.$$性质 2素数幂。若 $p$ 为素数且 $k \ge 1$则在 $1 \sim p^k$ 中恰好有 $p^k / p p^{k-1}$ 个数被 $p$ 整除其余均与 $p^k$ 互素$$\phi(p^k) p^k - p^{k-1}.$$性质 3互素积的积性。若 $a$ 与 $b$ 互素则$$\phi(ab) \phi(a) \cdot \phi(b).$$这条性质并不平凡其证明依赖中国剩余定理该定理保证对每个 $0 \le x a$ 和 $0 \le y b$存在唯一 $0 \le z ab$ 满足 $z \equiv x \pmod{a}$ 且 $z \equiv y \pmod{b}$。不难验证 $z$ 与 $ab$ 互素当且仅当 $x$ 与 $a$ 互素、$y$ 与 $b$ 互素因此与 $ab$ 互素的整数个数恰好等于与 $a$、$b$ 互素个数的乘积。性质 4一般情形的修正公式。对不互素的 $a, b$设 $d \gcd(a, b)$则有$$\phi(ab) \phi(a) \cdot \phi(b) \cdot \dfrac{d}{\phi(d)}.$$利用性质 13我们可以通过对 $n$ 做质因数分解来计算 $\phi(n)$。若 $n {p_1}^{a_1} \cdot {p_2}^{a_2} \cdots {p_k}^{a_k}$其中 $p_i$ 是 $n$ 的互异素因子则$$\begin{align} \phi (n) \phi ({p_1}^{a_1}) \cdot \phi ({p_2}^{a_2}) \cdots \phi ({p_k}^{a_k}) \ \left({p_1}^{a_1} - {p_1}^{a_1 - 1}\right) \cdot \left({p_2}^{a_2} - {p_2}^{a_2 - 1}\right) \cdots \left({p_k}^{a_k} - {p_k}^{a_k - 1}\right) \ p_1^{a_1} \cdot \left(1 - \frac{1}{p_1}\right) \cdot p_2^{a_2} \cdot \left(1 - \frac{1}{p_2}\right) \cdots p_k^{a_k} \cdot \left(1 - \frac{1}{p_k}\right) \ n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right) \end{align}$$即$\phi(n) n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$这是手算与实现时最常用的等价形式。单点计算基于分解的 $O(\sqrt n)$ 实现最直接的做法是枚举到 $\sqrt n$ 的因子遇到因子就反复除掉它同时应用公式 $n \cdot (1 - 1/p)$ 的增量形式result - result / iint phi(int n) { int result n; for (int i 2; i * i n; i) { if (n % i 0) { while (n % i 0) n / i; result - result / i; } } if (n 1) result - result / n; return result; }实现要点外层循环到 $\sqrt n$ 即止与普通质因数分解一致while循环把该素因子从 $n$ 中彻底除尽保证后续判定的是新的最小素因子循环结束后若n 1说明剩下的是大于 $\sqrt n$ 的大素因子需再执行一次result - result / nresult - result / i等价于result result * (1 - 1/i)且全程用整数运算避免了浮点误差。时间复杂度 $O(\sqrt n)$空间 $O(1)$。对 $n$ 很大但素因子很少的情况如 $n$ 是素数实际非常快若 $n$ 可达 $10^{12}$ 量级建议配合 Pollards Rho 分解 使用。批量计算 $1 \sim n$$O(n \log \log n)$ 筛法实现如果需要对 $1 \sim n$ 的所有数求 φ逐个分解是不可接受的。这里复用与埃拉托斯特尼筛法完全相同的思路不是为每个数逐一枚举素因子而是先找出所有素数再让每个素数去更新所有能被它整除的数的临时结果void phi_1_to_n(int n) { vectorint phi(n 1); for (int i 0; i n; i) phi[i] i; for (int i 2; i n; i) { if (phi[i] i) { for (int j i; j n; j i) phi[j] - phi[j] / i; } } }算法解读初始化 $\phi[i] i$与公式 $n \cdot \prod (1 - 1/p)$ 的初始因子 $n$ 对应若 $\phi[i] i$ 成立说明此前没有任何更小的素数更新过它即 $i$ 是素数判断方式与筛法标记素数同构对该素数 $i$遍历所有 $i$ 的倍数 $j$执行phi[j] - phi[j] / i即在每个倍数上乘入因子 $(1 - 1/i)$该过程与埃氏筛一致复杂度同为 $O(n \log \log n)$空间 $O(n)$。区间 $[L, R]$ 批量计算基于分段筛的实现当只需要区间 $[L, R]$ 的 φ 值如 $R - L 1$ 较小但 $R$ 很大时可用分段筛技术。其流程为用线性筛预计算出 $\sqrt{R}$ 以内的全部素数时间与空间均为 $O(\sqrt R)$对区间内每个数维护余数数组rem记录尚未分解完的部分并遍历这些素数、应用基于分解的 φ 公式若处理完所有小素数后rem仍大于 1说明存在大于 $\sqrt{R}$ 的大素因子在最后一遍统一处理。const long long MAX_RANGE 1e6 6; vectorlong long primes; long long phi[MAX_RANGE], rem[MAX_RANGE]; vectorint linear_sieve(int n) { vectorbool composite(n 1, 0); vectorint prime; // 0 and 1 are not composite (nor prime) composite[0] composite[1] 1; for(int i 2; i n; i) { if(!composite[i]) prime.push_back(i); for(int j 0; j prime.size() i * prime[j] n; j) { composite[i * prime[j]] true; if(i % prime[j] 0) break; } } return prime; } // To get the value of phi(x) for L x R, use phi[x - L]. void segmented_phi(long long L, long long R) { for(long long i L; i R; i) { rem[i - L] i; phi[i - L] i; } for(long long i : primes) { for(long long j max(i * i, (L i - 1) / i * i); j R; j i) { phi[j - L] - phi[j - L] / i; while(rem[j - L] % i 0) rem[j - L] / i; } } for(long long i 0; i R - L 1; i) { if(rem[i] 1) phi[i] - phi[i] / rem[i]; } }要点说明结果按偏移存储phi[x - L]即 $x$ 的欧拉函数值避免为整个 $[1, R]$ 开数组j max(i * i, (L i - 1) / i * i)是经典分段筛写法从不小于 $L$ 的 $i$ 的最小倍数开始同时避免重复处理 $i$ 的平方以内的部分rem数组模拟“剩余未分解部分”其存在使得同一个合数可以被不同素因子依次除尽而不影响 φ 的增量公式总复杂度为 $O((R - L 1)\log\log R \sqrt R)$其中 $\sqrt R$ 来自线性筛预处理区间部分与普通埃氏筛复杂度同阶。除数求和性质Gauss 定理Gauss 发现了欧拉函数一条优雅的性质对 $n$ 的所有正因子 $d$ 求和$$\sum_{d|n} \phi(d) n$$例如 10 的因子为 1、2、5、10则 $\phi(1) \phi(2) \phi(5) \phi(10) 1 1 4 4 10$。该性质同样可用于计算 $1 \sim n$ 的全部 φ 值实现比筛法版本更简洁代价是复杂度稍差为 $O(n \log n)$void phi_1_to_n(int n) { vectorint phi(n 1); phi[0] 0; phi[1] 1; for (int i 2; i n; i) phi[i] i - 1; for (int i 2; i n; i) for (int j 2 * i; j n; j i) phi[j] - phi[i]; }其正确性由除数求和公式的“反演”视角保证先设 $\phi[i] i - 1$ 作为初值随后每当 $i$ 是 $j$ 的因子就从 $\phi[j]$ 中减去 $\phi[i]$ 对应的重复贡献最终每个 $\phi[j]$ 恰好等于 $\sum_{d|j}\phi(d) - \sum_{d|j, dj}\phi(d) j - (j - \phi(j))$ 的差量关系下的正确结果。当 $n$ 在 $10^5 \sim 10^6$ 量级且追求实现极简时这是一个不错的替代方案。欧拉定理与费马小定理欧拉函数最重要的性质体现在欧拉定理中若 $a$ 与 $m$ 互素则$$a^{\phi(m)} \equiv 1 \pmod m$$当 $m$ 为素数时$\phi(m) m - 1$欧拉定理退化为费马小定理$$a^{m - 1} \equiv 1 \pmod m$$欧拉定理与欧拉函数在实践中有大量应用例如二者共同支撑了模逆元的计算当 $m$ 任意但与 $a$ 互素时 $a^{-1} \equiv a^{\phi(m)-1} \pmod m$当 $m$ 为素数时 $a^{-1} \equiv a^{m-2} \pmod m$配合快速幂二分指数可在 $O(\log m)$ 内求出逆元代价是 $m$ 非素数时需要先分解 $m$ 以计算 $\phi(m)$。欧拉定理还直接给出幂次化简等价式$$a^n \equiv a^{n \bmod \phi(m)} \pmod m$$这使得当 $n$ 极大甚至是另一次计算的巨大结果时可以先对 $n$ 取模 $\phi(m)$ 再计算 $x^n \bmod m$是处理“指数是天文数字”类问题的核心手段。群论视角$\phi(n)$ 恰是模 $n$ 乘法群 $(\mathbb Z / n\mathbb Z)^\times$ 的阶即单位群拥有乘法逆元的元素集合的大小而拥有乘法逆元的元素正是与 $n$ 互素的那些数。元素 $a$ 模 $n$ 的乘法阶$\operatorname{ord}_n(a)$ 定义为满足 $a^k \equiv 1 \pmod n$ 的最小正整数 $k$它等于 $a$ 生成的子群大小。由拉格朗日定理任何 $a$ 的乘法阶必整除 $\phi(n)$当 $\operatorname{ord}_n(a) \phi(n)$ 达到最大时$a$ 就是模 $n$ 的原根此时该乘法群是循环群。在原根的搜索算法见 primitive-root.md中第一步就是“计算 $\phi(n)$ 并分解它”随后只需验证对所有 $\phi(n)/p_i$$p_i$ 是 $\phi(n)$ 的素因子都有 $g^{\phi(n)/p_i} \not\equiv 1 \pmod n$此外模 $n$ 的原根个数恰为 $\phi(\phi(n))$。这些结论直接建立在本文章的公式之上。推广$x$ 与 $m$ 不互素时的高效幂次公式欧拉定理要求 $x$ 与 $m$ 互素。对任意 $x, m$ 以及满足 $n \geq \log_2 m$ 的指数存在一个较少为人知的推广公式$$x^{n}\equiv x^{\phi(m)[n \bmod \phi(m)]} \mod m$$证明概要设 $p_1, \dots, p_t$ 是 $x$ 与 $m$ 的公共素因子$k_i$ 是它们在 $m$ 中的指数令 $a p_1^{k_1} \dots p_t^{k_t}$则 $\frac{m}{a}$ 与 $x$ 互素。设 $k$ 为使 $a \mid x^k$ 成立的最小整数实际有 $k \le \log_2 m$当 $n \ge k$ 时$$\begin{align}x^n \bmod m \frac{x^k}{a}ax^{n-k}\bmod m \ \frac{x^k}{a}\left(ax^{n-k}\bmod m\right) \bmod m \ \frac{x^k}{a}\left(ax^{n-k}\bmod a \frac{m}{a}\right) \bmod m \ \frac{x^k}{a} a \left(x^{n-k} \bmod \frac{m}{a}\right)\bmod m \ x^k\left(x^{n-k} \bmod \frac{m}{a}\right)\bmod m \end{align}$$第三、四行的等价利用了恒等式 $ab \bmod ac a(b \bmod c)$若 $b cd r$ 且 $r c$则 $ab acd ar$ 且 $ar ac$。由于 $x$ 与 $\frac{m}{a}$ 互素可对 $x^{n-k}$ 应用欧拉定理得到高效公式$$x^n \bmod m x^k\left(x^{n-k \bmod \phi(\frac{m}{a})} \bmod \frac{m}{a}\right)\bmod m.$$该公式虽难直接套用但可用于分析序列 $(x^1 \bmod m, x^2 \bmod m, x^3 \bmod m, \dots)$ 的行为它在至多 $k$ 项之后进入长度为 $\phi\left(\frac{m}{a}\right)$ 的循环又因 $a$ 与 $\frac{m}{a}$ 互素时有 $\phi(a)\cdot\phi\left(\frac{m}{a}\right) \phi(m)$$\phi\left(\frac{m}{a}\right)$ 整除 $\phi(m)$故周期长度也可视为 $\phi(m)$。再结合 $\phi(m) \ge \log_2 m \ge k$即可化简出最终结论$$ x^n \equiv x^{\phi(m)} x^{(n - \phi(m)) \bmod \phi(m)} \bmod m \equiv x^{\phi(m)[n \bmod \phi(m)]} \mod m.$$这正是处理“幂塔”如 Codeforces 906D Power Tower、Kattis Exponial、LeetCode 372 Super Pow 等一类问题时的理论依据。仓库内的实际调用佐证在 cp-algorithms 仓库中$\phi$ 函数并非孤立概念而是被多个主题文档直接引用module-inverse.md欧拉定理公式 $a^{\phi(m)} \equiv 1 \pmod m$ 作为“利用快速幂求模逆元”方法的理论基础并指出计算 $\phi(m)$ 需要分解 $m$primitive-root.md原根搜索算法第一步即“计算 $\phi(n)$ 并分解之”且原根数量公式为 $\phi(\phi(n))$其实现代码generator中直接内嵌了对phi的分解逻辑burnside.mdBurnside 引理在环上染色问题中直接出现公式 $C_d \phi(n/d)$ 与 $\frac{1}{n}\sum_{d \mid n}\phi\left(\frac{n}{d}\right) k^d$将计数问题转化为 $\phi$ 的因子求和。读者如需验证代码可编译性可参照仓库 test 目录下各测试用例的组织方式与 test/extract_snippets.py 的代码片段抽取流程自行编写对应的 φ 函数单测。小结与练习建议场景推荐方法复杂度单个 $n$ 的 φ试除分解 result - result / i$O(\sqrt n)$$1 \sim n$ 全部 φ埃氏筛思想批量更新$O(n \log\log n)$$[L, R]$ 区间 φ线性筛 分段筛$O((R-L1)\log\log R \sqrt R)$$1 \sim n$ 全部 φ实现最简基于除数求和性质的增量减法$O(n \log n)$原文档的练习清单此处仅列题目名用于按图索骥自行检索SPOJ ETFEuler Totient Function、UVA 10179 Irreducible Basic Fractions、UVA 10299 Relatives、UVA 11327 Enumerating Rational Numbers、TIMUS 1673 Admission to Exam、UVA 10990 Another New Function、Codechef COZIE、SPOJ LCMSUM、GYM 100975(F)、UVA 13132 Laser Mirrors、SPOJ GCDEX、UVA 12995 Farey Sequence、SPOJ TIP1、LOJ 1007 Mathematically Hard、SPOJ DCEPCA03、SPOJ NAJPWG、SPOJ DCEPC12G、SPOJ INVPHI、Codeforces 906D Power Tower、Kattis Exponial、LeetCode 372 Super Pow、Codeforces 776E The Holmes Children、Codeforces 1900D Small GCD。建议按 “单点计算 → 批量筛法 → 幂次化简 → 非互素推广” 的路径逐个消化理解每一步的复杂度来源与公式推导。赞分享文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载相关推荐10分钟快速上手 GhostTrack终端位置追踪 OSINT 工具保姆级指南10分钟快速上手 GhostTrack终端位置追踪 OSINT 工具保姆级指南 GhostTrack 是一个完全在终端里运行的轻量 OSINT 工具支持 I网络安全CLINetworkX 欧拉图算法指南欧拉回路、欧拉路径与 eulerize 的完整实战解析NetworkX 欧拉图算法指南欧拉回路、欧拉路径与 eulerize 的完整实战解析 导读 本文围绕 NetworkX 中 networkx.algorit图计算数据分析科学计算欧拉函数 φ(n) 详解与多语言实现从单值计算到筛法批量求值Cosmos 项目实战欧拉函数 φ n 详解与多语言实现从单值计算到筛法批量求值Cosmos 项目实战 欧拉函数Eulers totient function又称 phi教程示例工程上一篇ik_llama.cpp AVX2 Flash Attention 实现解析寄存器约束下的 CPU 注意力加速方案下一篇GBrain 的 Brain-Agent LoopAgent 记忆读写闭环的完整协议与实战指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考