模逆元
2026-07-29
定义
如果 ab≡1(modm),称 b 为 a 关于 m 的乘法逆元,记作 a−1。
逆元存在当且仅当 gcd(a,m)=1。
求逆元
扩展欧几里得
构造 ax+my=1,使用 exgcd 求出一组通解 x0,y0,把 x 规范到 [0,m) 即可。
int inv(int a , int MOD) {
int x , y; exgcd(a , MOD , x , y);
return (x % MOD + MOD) % MOD;
}费马小定理与快速幂
费马小定理告诉我们,当 p 为质数且不整除 a 时,ap−1≡1(modp),我们将其同时乘 a−1,得到 a−1≡ap−2(modp)。
因此,直接使用快速幂计算 ap−2 即可。
线性递推
若 p 为质数,且 2≤i<p,可以利用更小逆元递推出 i 的逆元:
i−1≡−⌊ip⌋×(pmodi)−1(modp)
证明
我们设 p=qi+r,其中 q=⌊ip⌋,r=pmodi,模 p 后,显然有:
qi+r≡0(modp)⟹qi≡−r(modp)
由于 p 为质数,并且 2≤i<p,则 i,r 都存在逆元,两边同乘 i−1r−1 ,得到:
qr−1≡−i−1(modp)⟹i−1≡−qr−1(modp)
带入 q,r 即为原式,其中 0≤r<i,它的逆元已经求出。
void init() {
inv[1] = 1;
for(int i = 2 ; i <= n ; i ++) {
inv[i] = (p - p/i) * inv[p % i] % p;
}
}时间复杂度 O(n),必须保证 p>n。
线性递推阶乘求逆元
我们可以求出 1∼n 的阶乘,通过快速幂求出 n! 的逆元后依次求出每个数的逆元。
void init() {
fac[0] = 1;
for(int i = 1 ; i <= n ; i ++)
fac[i] = fac[i-1] * i % MOD;
invfac[n] = qpow(fac[n] , MOD-2 , MOD);
for(int i = n ; i >= 1 ; i --) {
invfac[i-1] = invfac[i] * i % MOD;
inv[i] = invfac[i] * fac[i-1] % MOD;
}
}