欧拉函数与组合数
欧拉函数（Euler's Totient Function，记 φ(n)）是数论里刻画「互质」的核心工具——统计 1..n 中与 n 互质（gcd = 1）的个数。它由积性性质导出通项公式 φ(n) = n × Π(1 - 1/p)（p 遍历 n 的质因子），对质数 p 退化成漂亮的 φ(p) = p - 1，对质数幂 p^k 则是 p^k - p^(k-1)。更关键的是欧拉定理：当 gcd(a, n) = 1 时 a^φ(n) ≡ 1 (mod n)——它一举把「大指数幂取模」降为 a^(e mod φ(n))，是快速幂 + 模算术的理论基石，也是 RSA 公钥密码的数学根。
与它成对出现的是组合数 C(n, k)（从 n 个里选 k 个的方案数），公式 n! / (k! × (n-k)!)。组合数取模有三大套路：①杨辉三角递推 C(n,k) = C(n-1,k-1) + C(n-1,k)，适合 n 小、要全表；②预处理阶乘 + 乘法逆元做到 O(1) 单点查询（逆元用费马小定理 a^(p-2) mod p 当 p 为质数，或欧拉定理 a^(φ(m)-1) mod m 一般情形）；③**卢卡斯定理（Lucas）**处理 n, k 极大但模数 p 小（且为质数）时 C(n,k) mod p。这套「欧拉函数 → 欧拉定理 → 逆元 → 组合数取模」的链条，是竞赛与面试中模算术的核心考点。
评价
优点
- 理论统一：欧拉定理把费马小定理（质数情形）纳入同一框架，逆元、降幂、RSA 都由它派生，理解一个等于理解一串
- 计算高效：单值
φ(n)用质因数分解O(√n)；筛法求φ(1..n)用埃氏筛O(n log log n)；组合数预处理后O(1)查询——都能应对大输入 - 组合数公式灵活：递推（全表）/ 公式+逆元（单点 O(1)）/ 卢卡斯（大数小模）三种打法覆盖所有取模场景
- 应用面广：分数取模（除法转乘逆元）、大指数降幂、RSA 加解密、概率/计数题取模都离不开它
缺点
- 前提多易错：费马求逆元要求模数是质数、欧拉求逆元要求互质，不满足时无解或需扩欧；降幂要分
gcd是否为 1 两种情况 - 阶乘预处理有范围：
O(1)查询依赖n!预处理，n超过模数p时阶乘含因子p会变 0，需卢卡斯或分解质因子 - 中间乘法易溢出：模算术中
a × b mod m在a, b接近m时可能溢出 64 位，需用__int128或快速乘 - 卢卡斯仅限质数模：模数非质数时卢卡斯失效，需更复杂的扩展卢卡斯（exLucas）
本叶地图
- 入门 —— φ(n) 定义与公式、欧拉定理、组合数 C(n,k) 公式、互质与逆元的直觉
- 欧拉函数：计算与欧拉定理 —— φ(n) 通项公式、单值 O(√n) 计算、埃氏筛求 φ(1..n)、欧拉定理与费马小定理关系
- 组合数与逆元 —— 杨辉三角递推、阶乘+逆元 O(1) 查询、卢卡斯定理、乘法逆元（费马/欧拉）
- 参考 —— φ/组合数代码模板、复杂度表、易错点、权威链接
交互演示
- 欧拉函数可视化演示 —— φ(n) 的定义与
1..n中互质个数的可视化（组合数部分无专门可视化，见正文公式与递推）