欧拉函数 φ(n)：
小于或等于 n 的正整数中与 n 互质的数的个数。
对于质因数分解 n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ，有公式：
φ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × ... × (1 - 1/pₖ)
或等价地：
φ(n) = p₁^(a₁-1) × (p₁-1) × p₂^(a₂-1) × (p₂-1) × ... × pₖ^(aₖ-1) × (pₖ-1)
约数和函数 σ(n)：
n 的所有正约数之和。
对于质因数分解 n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ，有公式：
σ(n) = (p₁^(a₁+1) - 1)/(p₁ - 1) × (p₂^(a₂+1) - 1)/(p₂ - 1) × ... × (pₖ^(aₖ+1) - 1)/(pₖ - 1)
约数个数函数 τ(n)：
n 的正约数的个数。
对于质因数分解 n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ，有公式：
τ(n) = (a₁ + 1) × (a₂ + 1) × ... × (aₖ + 1)
特殊性质：
- 质数 p：φ(p) = p - 1, τ(p) = 2, σ(p) = p + 1
- 质数幂 p^k：φ(p^k) = p^(k-1) × (p-1), τ(p^k) = k + 1
- 完全平方数：τ(n) 为奇数
- 完全数：若 σ(n) = 2n，则 n 为完全数（如 6, 28, 496）
- 积性函数：φ, τ, σ 都是积性函数，即若 gcd(a,b)=1，则 f(ab)=f(a)×f(b)
应用场景：
- 密码学：RSA 算法中使用欧拉函数计算私钥
- 数论：欧拉定理：若 gcd(a,n)=1，则 a^φ(n) ≡ 1 (mod n)
- 组合数学：计算本原根、循环群的阶等
- 竞赛编程：快速幂、模运算优化等
时间复杂度：
O(√n) 用于质因数分解，计算各函数值为 O(k)，其中 k 为不同质因子个数