模逆元 $ a^{-1} \bmod m $ 存在当且仅当 $ \gcd(a, m) = 1 $，即 $ a $ 与 $ m $ 互质；这是逆元存在的充要条件，不满足则无解，不可强行计算。
模逆元存在的前提是什么
模逆元 a⁻¹ mod m 存在，当且仅当 gcd(a, m) == 1。这不是可选条件，而是数学硬约束——如果 gcd(a, m) != 1，extend_gcd 虽然仍能跑出结果，但那个结果不能当作模逆元用。实际编码时必须先检查，否则后续计算全错。
- 用
__gcd(a, m)（GCC）或自己写gcd()判断 - 若不互质，直接返回错误码（如 -1）或抛异常，别试图“强行取模”
- 注意：负数取模行为依赖语言实现，C++ 中
a % m符号随a，所以建议先做a = (a % m + m) % m归一化
如何用 extend_gcd 得到正确的逆元值
扩展欧几里得算法解的是 a <em> x + m </em> y = gcd(a, m)。当 gcd(a, m) == 1 时，该式变为 a <em> x + m </em> y = 1，两边对 m 取模，立刻得到 a * x ≡ 1 (mod m)，所以 x 就是逆元——但这个 x 可能为负或大于 m。
- 调用后必须对
x做模调整：x = (x % m + m) % m - 不要只写
(x % m)：C++ 中-5 % 7是-5，不是2 -
extend_gcd返回的x和y是任意一组解，通解是x + k*m，所以调整一次就够了
long long extend_gcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1; y = 0;
return a;
}
long long g = extend_gcd(b, a % b, y, x);
y -= a / b * x;
return g;
}
<p>long long mod_inv(long long a, long long m) {
long long x, y;
long long g = extend_gcd(a, m, x, y);
if (g != 1) return -1; // 无逆元
return (x % m + m) % m;
}为什么不用 pow(a, m-2, m)？
有人想套费马小定理：若 m 是质数，则 a^(m-2) mod m 是逆元。但这有三个硬限制：
-
m必须是质数，而实际场景中模数常是合数（比如1e9+7是质数，但1000000008不是） - 即使
m是质数，a还得满足a % m != 0，否则无定义 - 快速幂比
extend_gcd多一次O(log m)运算，且需额外处理大指数溢出（long long乘法中间结果易爆）
extend_gcd 无质数要求、时间稳定、空间更省，是通用首选。
立即学习“C++免费学习笔记（深入）”；
int 和 long long 混用会踩什么坑
最常见的是中间乘法溢出：比如 a 和 m 接近 INT_MAX，在 extend_gcd 递归中 a / b * x 这一步就可能溢出。
- 所有参与运算的变量（包括参数、临时变量、返回值）统一用
long long - 不要传
int给期望long long的函数，隐式转换救不了溢出 - 如果输入是
int，调用前显式转：mod_inv((long long)a, (long long)m)
逆元本身虽在 [0, m) 范围内，但计算过程中的系数 x、y 绝对值可能远超 m，这是算法本质决定的——别想着用 int 省空间。
