逆元

逆元参考博客

费马小定理参考博客

x在模p意义下存在逆元,当且仅当x与p互质。

利用费马小定理求逆元

费马小定理:

  • 对于质数p,对于任意整数a,均满足: $a^p \equiv a$ mod(p)

移项后得:$a(a^{p-1} - 1) \equiv 0$ mod(p)

所以:$a^{p-1} \equiv 1$ mod(p)

即:$a \times a^{p-2} \equiv 1$ mod(p)

因此a在模p意义下的逆元就是$a^{p-2}$

1
ll inv(ll a, ll p) { return Pow(a, p - 2); }

扩展欧几里得求逆元

$ax \equiv 1$ mod(p)

-> $ax + py = 1$

当a与p互质时,上式有解,直接扩展欧几里得求出x

1
2
3
4
5
ll inv(ll a, ll p) {
ll x, y;
ll d = ex_gcd(a, p, x, y);
return d == 1 ? (x % p + p) % p : -1;
}

线性递推逆元

1! ~ n!的逆元

证明:

$fac[i] \times inv[i] \equiv 1$ mod(p)

-> $fac[i+1] \times (i+1) \times inv[i+1] \equiv 1$ mod(p)

-> $inv[i] = inv[i+1] \times (i+1)$

1
2
3
4
5
6
getInv(int n) {
f[0] = 1;
for (int i = 1; i < n; i++) f[i] = f[i - 1] * i % mod;
inv[n - 1] = Pow(f[n - 1], mod - 2);
for (int i = n - 2; ~i; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
}

1 ~ n的逆元

证明:

s = p // i,t = p % i,则有s * i + t = p

因此$s * i + t \equiv 0 $ mod(p)

同时除以i * t

$inv[i] \equiv -s \times inv[t]$ mod(p)

s = p // i,t = p % i 带入得

$inv[i] \equiv inv[p\%i] \times \frac{-p}{i}$ mod(p)

1
2
3
getInv(int n) {
for (int i = 2; i < n; i++) inv[i] = inv[mod % i] * (mod - mod / i) % mod;
}