illegalCreed

中文

English

中文

English

Appearance

欧拉函数：计算与欧拉定理 ​

基于通用数论套路 · 核于 2026-07

速查 ​

  • 通项公式：n = Π pi^ai 时 φ(n) = n × Π(1 - 1/pi)——计算 φ 的根本公式，由积性 + 容斥导出。
  • 特殊值：质数 φ(p) = p-1；质数幂 φ(p^k) = p^(k-1) × (p-1)；φ(1) = 1。
  • 积性：gcd(a,b)=1 ⇒ φ(a×b) = φ(a)×φ(b)——通项公式成立的理论依据。
  • 单值计算：对 n 做 O(√n) 质因数分解，每发现一个质因子 p 就 φ = φ / p × (p-1)，全程整数运算。
  • 筛法求 φ(1..n)：埃氏筛，对每个质数 p 把它所有倍数 m 执行 φ[m] = φ[m] / p × (p-1)，整体 O(n log log n)。
  • 欧拉定理：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）。
  • 降幂完整版：gcd(a,n)≠1 时不能直接 e mod φ(n)，要用扩展欧拉定理 a^e ≡ a^(e mod φ(n) + φ(n)) (mod n)（当 e ≥ φ(n)）。
  • 代码三件套：快速幂（配合降幂）、单值 φ（质因数分解）、埃氏筛 φ（批量）。
  • 易错：先除后乘避免分数（φ / p × (p-1) 而非 φ × (p-1) / p）；费马求逆要求质数模数。

一、通项公式回顾 ​

上一节已经给出 φ(n) = n × Π(1 - 1/pi)（pi 遍历 n 的不同质因子）。它依赖 φ 的积性：

若 gcd(a, b) = 1，则 φ(a × b) = φ(a) × φ(b)。

注意积性不要求 a, b 是质数，只要求它们互质。对 n 做标准分解后，各质数幂两两互质，于是 φ(n) 等于各 φ(pi^ai) 之积；而对质数幂 φ(p^k) = p^k - p^(k-1) = p^k × (1 - 1/p)，乘起来就得到通项公式。

二、单值计算：O(√n) 质因数分解 ​

要算单个 φ(n)，只需对 n 做质因数分解（试除到 √n），每碰到一个质因子 p，把答案乘上 (1 - 1/p)。为了全程整数运算，写成 先除后乘：

js
// 单值欧拉函数：O(√n)
function phi(n) {
  let res = n;
  for (let p = 2; p * p <= n; p++) {     // 试除到 √n
    if (n % p === 0) {                    // p 是 n 的质因子
      while (n % p === 0) n = n / p;      // 把 n 里的 p 全除掉
      res = res / p * (p - 1);            // ← 先除后乘，避免分数
    }
  }
  if (n > 1) res = res / n * (n - 1);     // 剩下的大于 1 的因子是质数
  return res;
}

为什么先除后乘：在循环到 p 时，res 里还含因子 p（来自初始的 n），res / p 是整除；若先 res * (p-1) 再除，中间结果可能不是 p 的倍数导致除不尽。这是最高频的坑。

验证 phi(6)：res=6；p=2 整除，n 除成 3，res = 6/2×1 = 3；p*p=4 > 3 退出循环；n=3>1，res = 3/3×2 = 2。✓

三、筛法求 φ(1..n)：埃氏筛 ​

当需要 φ(1), φ(2), ..., φ(N) 全表时，逐个用 O(√n) 分解太慢（总 O(N√N)）。用埃氏筛思想批量算，总复杂度 O(N log log N)：

js
// 埃氏筛求 phi[1..N]
function sievePhi(N) {
  const phi = Array.from({ length: N + 1 }, (_, i) => i); // 初始化 phi[i]=i
  for (let p = 2; p <= N; p++) {
    if (phi[p] === p) {                   // p 是质数（未被更小的质数改过）
      for (let m = p; m <= N; m += p) {   // 遍历 p 的所有倍数
        phi[m] = phi[m] / p * (p - 1);    // 同样先除后乘
      }
    }
  }
  return phi;
}

原理：初始化 phi[i] = i，对每个质数 p，把它的倍数 m 都乘上 (1 - 1/p)——这正好就是通项公式对每个质因子的贡献。一个合数 m 会被它所有质因子各处理一次，最终 phi[m] = m × Π(1-1/p)。

四、欧拉定理与降幂 ​

定理：gcd(a, n) = 1 ⇒ a^φ(n) ≡ 1 (mod n)。

直接推论是降幂（前提 gcd(a,n)=1）：

a^e ≡ a^(e mod φ(n)) (mod n)

配合快速幂就能算超大指数：

js
// 快速幂 a^e mod m：O(log e)
function powmod(a, e, m) {
  a = ((a % m) + m) % m;
  let res = 1n;
  if (typeof a === 'number') { a = BigInt(a); e = BigInt(e); m = BigInt(m); }
  let base = a, exp = e, mod = m;
  while (exp > 0n) {
    if (exp & 1n) res = res * base % mod;
    base = base * base % mod;
    exp >>= 1n;
  }
  return Number(res);
}
// 降幂：3^100 mod 7，gcd(3,7)=1
// phi(7)=6，100 mod 6 = 4，3^4=81 ≡ 4 (mod 7)

扩展欧拉定理（gcd ≠ 1 时） ​

当 gcd(a, n) ≠ 1 且指数 e 很大时，不能直接 e mod φ(n)。此时用扩展形式（e ≥ φ(n) 时）：

a^e ≡ a^(e mod φ(n) + φ(n)) (mod n)        // 仅当 e ≥ φ(n)

即指数 e 超过 φ(n) 时，先对 φ(n) 取模再加回 φ(n)。常见于「巨大幂塔」或 a 与模数共享因子的题。

五、与费马小定理的关系 ​

把欧拉定理的 n 取成质数 p：φ(p) = p - 1，于是

a^(p-1) ≡ 1 (mod p)        // 费马小定理，p 质数且 p 不整除 a

所以费马小定理是欧拉定理的特例。实战中：

  • 模数是质数 → 直接用费马（更简单，a^(p-2) 求逆元）。
  • 模数任意 → 用欧拉（需先算 φ(m)，逆元是 a^(φ(m)-1)）。

二者都要求 gcd(a, 模数) = 1，否则定理不成立、逆元不存在。

交互演示 ​

下一步 ​

φ 与欧拉定理就绪后，组合数取模的「阶乘 + 逆元 O(1) 查询」与「卢卡斯定理」都建立在它们之上，见组合数与逆元。