入门：欧拉函数、欧拉定理与组合数公式
基于通用数论概念 · 核于 2026-07
速查
- φ(n) 定义：欧拉函数
φ(n)=1..n中与n互质（gcd(i, n) = 1）的正整数个数；约定φ(1) = 1。 - φ(质数)：质数
p与1..p-1全都互质，故φ(p) = p - 1（如φ(7) = 6）。 - φ(质数幂)：
φ(p^k) = p^k - p^(k-1) = p^(k-1) × (p - 1)（p^k里只有p的倍数不互质，共p^(k-1)个）。 - φ 通项公式：若
n = p1^a1 × p2^a2 × ... × pk^ak，则φ(n) = n × Π(1 - 1/pi)——由积性 + 容斥导出，是计算 φ 的根本公式。 - 积性函数：
gcd(a, b) = 1时φ(a×b) = φ(a) × φ(b)，这是通项公式成立的理论依据。 - 欧拉定理：当
gcd(a, n) = 1时，a^φ(n) ≡ 1 (mod n)——大指数降幂的根：a^e ≡ a^(e mod φ(n)) (mod n)。 - 费马小定理（欧拉特例）：
n为质数p时φ(p) = p-1，欧拉定理退化为a^(p-1) ≡ 1 (mod p)（p ∤ a）。 - 组合数 C(n,k) 定义：从
n个不同元素里选k个（不考虑顺序）的方案数，0 ≤ k ≤ n，否则为 0。 - 组合数公式：
C(n,k) = n! / (k! × (n-k)!)——阶乘之比；C(n,k) = C(n,n-k)对称。 - 杨辉三角递推：
C(n,k) = C(n-1,k-1) + C(n-1,k)，边界C(n,0) = C(n,n) = 1——O(n²) 建全表。 - 乘法逆元：
a × a⁻¹ ≡ 1 (mod m)，把「除以 a」转成「乘 a⁻¹」；存在当且仅当gcd(a, m) = 1。 - 逆元求法：模数
p质数 → 费马a⁻¹ = a^(p-2) mod p；一般模m→ 欧拉a⁻¹ = a^(φ(m)-1) mod m（需互质）。 - 进阶顺序：欧拉函数：计算与欧拉定理 → 组合数与逆元 → 参考。
一、欧拉函数 φ(n)：到底在数什么
欧拉函数回答一个朴素问题：「1 到 n 里，有多少个数和 n 互质？」 互质即最大公约数为 1（gcd(i, n) = 1）。
φ(1) = 1：只有 1 自己，gcd(1,1)=1，约定算 1 个。φ(6) = 2：1..6里与 6 互质的是1, 5，共 2 个（2/3/4/6 都与 6 有大于 1 的公约数）。φ(7) = 6：7 是质数，1..6全与它互质。φ(8) = 4：8 = 2^3，1..8里奇数1,3,5,7与它互质，共 4 个（偶数都与 8 共享因子 2）。
质数与质数幂的快速结论
| n 的形式 | φ(n) | 直觉 |
|---|---|---|
质数 p | p - 1 | 1..p-1 全互质 |
质数幂 p^k | p^(k-1) × (p-1) | 只有 p, 2p, 3p, ...（共 p^(k-1) 个）不互质 |
两互质数之积 a×b（gcd=1） | φ(a) × φ(b) | 积性性质 |
「质数幂里不互质的就是 p 的倍数」这一观察是记忆 φ(p^k) = p^k - p^(k-1) 的关键。
二、通项公式：n × Π(1 - 1/p)
对任意 n = p1^a1 × p2^a2 × ... × pk^ak（标准分解），欧拉函数有统一的乘积公式：
φ(n) = n × (1 - 1/p1) × (1 - 1/p2) × ... × (1 - 1/pk)它由两件事推出：①积性（互质因子可拆开相乘）；②容斥（质数幂 p^k 里扣掉 p 的倍数）。验证 φ(6)：6 = 2 × 3，φ(6) = 6 × (1-1/2) × (1-1/3) = 6 × 1/2 × 2/3 = 2 ✓。
计算意义：只要对 n 做质因数分解，就能用这个公式 O(√n) 算出 φ(n)（每个质因子 p 贡献一次 × (1-1/p) = × (p-1) / p，用整数运算 φ = φ / p × (p-1) 避免浮点）。
三、欧拉定理：大指数取模的「降幂咒语」
定理：若 gcd(a, n) = 1，则 a^φ(n) ≡ 1 (mod n)。
它的威力在于「降幂」：任何指数 e 都可以先用 φ(n) 取模——
a^e ≡ a^(e mod φ(n)) (mod n) // 当 gcd(a,n) = 1例：算 3^100 mod 7。φ(7) = 6，gcd(3,7)=1，故 3^100 ≡ 3^(100 mod 6) = 3^4 = 81 ≡ 4 (mod 7)。原本要算 100 次方，现在只算 4 次方。
与费马小定理的关系
当 n 恰好是质数 p 时，φ(p) = p - 1，欧拉定理退化成：
a^(p-1) ≡ 1 (mod p) （费马小定理，p 质数且 p ∤ a）所以费马小定理是欧拉定理在「模数为质数」时的特例——记住欧拉定理，费马自动到手。
四、组合数 C(n,k)：从 n 选 k
组合数 C(n, k)（也写作 C_n^k 或 n 个不同元素里选 k 个、不考虑顺序」的方案数。
- 公式：
C(n,k) = n! / (k! × (n-k)!)。例如C(5,2) = 120 / (2 × 6) = 10。 - 对称性：
C(n,k) = C(n,n-k)（选 k 个等于选 n-k 个不选）。 - 边界：
C(n,0) = C(n,n) = 1（不选 / 全选都只有一种）；k > n时C(n,k) = 0。
三种取模打法（预告）
| 场景 | 方法 | 复杂度 |
|---|---|---|
n 小（≤ 几千）、要全表 | 杨辉三角递推 | O(n²) 建表 |
n 中等、模数质数、单点查 | 预处理阶乘+逆元 | 预处理 O(n)，查询 O(1) |
n, k 极大、模数 p 小且质数 | 卢卡斯定理 | O(log_p n) |
五、乘法逆元：把「除法」搬进模算术
模算术里没有真正的除法——「a / b mod m」不能用普通除法（结果不是整数）。解法是找 b 的乘法逆元 b⁻¹，满足 b × b⁻¹ ≡ 1 (mod m)，于是 a / b ≡ a × b⁻¹ (mod m)。
逆元存在的充要条件是 gcd(b, m) = 1（不互质则无逆元，除法无意义）。求逆元的两条主路（都来自欧拉定理家族）：
- 费马求逆（模数
p是质数）：b⁻¹ ≡ b^(p-2) (mod p)——直接套费马小定理，配快速幂O(log p)。 - 欧拉求逆（模数
m任意，但需gcd(b,m)=1）：b⁻¹ ≡ b^(φ(m)-1) (mod m)——套欧拉定理。
这就是为什么组合数公式 C(n,k) = n! / (k!(n-k)!) 在模质数 p 下能算：把分母 k!(n-k)! 用逆元换成「乘上它的逆元」，预处理 fact[i] 与 invfact[i] 后 C(n,k) = fact[n] × invfact[k] × invfact[n-k] mod p，O(1) 查询。
下一步
理解了 φ 的定义、欧拉定理的降幂与逆元后，下一步深入φ 的两种计算方法（单值 O(√n) + 埃氏筛 O(n log log n)）与欧拉定理的代码落地，见欧拉函数：计算与欧拉定理。