费马小定理求逆元要求模数p为质数且a与p互质，否则a^(p-2) mod p不满足a·inv(a)≡1(mod p)，结果无意义；非质数模下应改用扩展欧几里得算法。
费马小定理求逆元在模数不是质数，或待求逆元的数与模数不互质时直接失效——它根本不会返回正确结果，而是算出一个无意义的数。
为什么 pow_mod(a, p-2, p) 有时返回错值
费马小定理成立的前提是：p 为质数，且 gcd(a, p) == 1。只要破坏任一条件，a^(p-2) % p 就不再满足 a * inv(a) % p == 1。
- 当
p是合数（比如p = 1000000008），即使a和p互质，a^(p-2) % p也不等于逆元（此时应改用欧拉定理：指数换为phi(p)-1，但phi(p)难算） - 当
a和p不互质（比如a = 4,p = 6），逆元根本不存在，但pow_mod(4, 4, 6)仍会返回4，而4 * 4 % 6 == 4 ≠ 1—— 完全无效 - 常见误用场景：把题目给的
MOD = 10^9+7当成万能模数，却没注意题干悄悄换成MOD = 998244353（仍是质数，没问题），或更隐蔽地用了MOD = 1000000009（也是质数），但若写成1000000000就崩了
遇到非质数模数时该用什么替代
当 p 是合数但 gcd(a, p) == 1 时，逆元依然存在，只是不能靠费马小定理。此时优先选扩展欧几里得算法：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
-
extgcd(a, p, x, y)返回g = gcd(a, p)，并令a*x + p*y == g - 若
g != 1，说明逆元不存在，直接报错或跳过 - 若
g == 1，则x % p（需调整为正数）就是a模p的逆元 - 相比费马小定理，它不依赖模数是否为质数，只依赖互质性，且时间复杂度同为
O(log min(a,p))
快速幂实现中容易被忽略的溢出点
即使模数是质数，a 很大时，pow_mod 内部乘法仍可能溢出 int 或 long long：
- 错误写法：
ret = ret * a % p—— 若ret和a都接近1e9，相乘会超long long上限（约9e18） - 安全写法：必须用
__int128（GCC 支持）或分段乘法（如mul_mod函数）做中间乘法取模 - 典型坑：
pow_mod(1e9, 1e9+5, 1e9+7)看似合法，但中间a*a可达1e18，再乘一次就爆long long - 竞赛常用防御：统一用
typedef long long ll，并在乘法处显式调用mul_mod(a, b, p)
真正麻烦的不是“怎么算”，而是“要不要算”——每次调用前检查 gcd(a, p) == 1 成本很低，但很多人跳过这步，直到样例通过、现场 WA 才发现逆元压根不存在。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
