核心概述
欧拉函数 φ(n)：统计 1..n 中与 n 互质的个数；可由因子分解式 n·∏(1−1/p) 单点计算，或用线性筛在 O(N) 批量预处理。
原文引述
Description: Euler’s totient φ(n) counts integers ≤ n that are coprime to n. Multiplicative with φ(p^k)=p^k−p^{k−1}. Compute by factoring n or via linear sieve for 1..N. Time: Single n via factoring ~ O(∑ log p); sieve O(N)
展开阐述
-
函数/接口（据实现）
- long long phi(long long n)：对单点 n，先分解 n 的质因子集合 {p}，返回 n·∏(1−1/p)。
- vector
phiSieve(int N)：线性筛返回 1..N 的 φ 值数组（同时可产出 primes）。 - 可选：long long coprimeCountUpTo(long long n, long long m)：统计 ≤m 与 n 互质个数（用容斥按 n 的不同质因子）。
-
单点算法（因子分解式）
- ans ← n。
- 枚举 n 的不同质因子 p：ans = ans / p * (p − 1)。
- 返回 ans。分解可用试除、spf、或 084-数论-因数分解（Rho+MR）。
- 说明：仅对“不同”的质因子做一次更新。
-
批量算法（线性筛 φ）
- 维护 primes 与 phi 数组：
- phi[1]=1。
- 对 i=2..N：
- 若 i 为新质数 p：primes.push_back(p)，phi[i]=i−1。
- 对每个 p∈primes：
- 若 i·p>N 终止。
- 若 p | i：phi[i·p]=phi[i]*p；break。
- 否则（p ∤ i）：phi[i·p]=phi[i]*(p−1)。
- 复杂度 O(N)，适合多次查询或需要前缀和。
- 维护 primes 与 phi 数组：
-
常用恒等式与应用
- ∑_{d|n} φ(d) = n（约数和恒等式）。
- 与幂/模运算：a^{φ(m)}≡1 (mod m) 当 gcd(a,m)=1（欧拉定理；素数模退化为费马小定理）。
- 计数应用：循环节长度、互质对计数、分数最简化个数等。
-
输出语义
- phi(n)：返回与 n 互质的个数。
- phiSieve(N)[x]：1..N 的 φ(x)。
-
复杂度
- 单点：因子分解主导；用试除 O(√n)，用 Rho 对 64 位通常毫秒级。
- 批量：线性筛 O(N) 时间、O(N) 空间。
-
使用与注意
- 大数场景优先用 084-数论-因数分解（配 087-数论-米勒拉宾 与 090-数论-长整型模乘）获取不同质因子。
- 批量预处理与多次查询结合时，线性筛更高效（参见 085-数论-快速筛 的 phi 版本）。
- 注意 64 位乘法溢出，必要时使用 128 位中间量或取模（见 094-数论-模运算）。