欧拉函数与模运算
本节目标
用快速幂、欧拉函数和费马小定理处理同余计算。
识别信号
题目要求大幂次的余数、模意义下的除法，或统计与一个数互质的余数数量时，应先转到同余关系。指数很大不是逐次乘法的信号，而是把指数按二进制拆分的信号。
核心定义与不变量
a ≡ b (mod m) 表示二者除以 m 的余数相同。快速幂始终维护“已选二进制位的乘积”与“当前位对应的幂”都已取模。欧拉函数 φ(n) 统计 1..n 中与 n 互质的数；每个不同质因子 p 都使答案乘上 (p-1)/p。
模意义下的除法不是普通整数除法：只有 x 在模 m 下存在逆元 x⁻¹ 时，a / x 才能写成 a · x⁻¹。费马小定理的逆元公式 x^(p-2) 只适用于模数 p 为质数且 x mod p ≠ 0。
朴素方法与瓶颈
循环乘 b 次计算 a^b 是 O(b)；逐个检查 1..n 是否与 n 互质是 O(n log n)。当指数或整数达到题目上界时，两者都无法承担。
推导与实现框架
快速幂每轮读取指数最低位：最低位为 1 就把当前底数乘进答案，然后平方底数、右移指数。欧拉函数试除每个候选质因子；一旦整除，只应用一次 result = result / p * (p - 1)，再除尽该因子。逆元题先排除余数为零，再调用快速幂。
复杂度与数值边界
快速幂和费马逆元为 O(log p)；单个欧拉函数为 O(√n)。本栏两道快速幂题均有 p≤2×10^9，底数和答案取模后都小于 p，二者乘积小于 4×10^18，可由标准 C++17 的 long long 安全保存。若其他题目的模数可能更大，就必须另用可移植模乘，不能照搬这里的乘法。Python 整数不受固定宽度限制。
母题序列
常见误区
把 / 直接写进取模表达式、对同一质因子重复更新欧拉函数，或忽略 value % prime == 0 时逆元不存在。快速幂也不能先让乘积在窄整数类型中溢出再取模。
迁移方向
组合数预处理会直接复用快速幂逆元；更一般的扩展欧几里得、线性同余方程和中国剩余定理不属于本章范围。