逆元就是用来解决大数除法取模计算的

取模规则

a+b(modp)=(amodp+bmodp)modpa + b \pmod{p} = (a \bmod{p} + b \bmod{p}) \bmod{p}

ab(modp)=(amodpbmodp)modpa - b \pmod{p} = (a \bmod{p} - b \bmod{p}) \bmod{p}

a×b(modp)=(amodp×bmodp)modpa \times b \pmod{p} = (a \bmod{p} \times b \bmod{p}) \bmod{p}

ab(modp)(amodpbmodp)modp\frac{a}{b} \pmod{p} \neq (\frac{a \bmod{p}}{b \bmod{p}}) \bmod{p}

逆元定义

根据取模规则可以发现,对于

ab(modp)\frac{a}{b} \pmod{p}

bb 非常大时,因为无法拆分取模,结果难以计算,这时就需要逆元。逆元本质就是把除法取模转换为乘法以便于拆分计算

我们知道:

a×b=1 b  a b=1a若 a \times b = 1,则\ b\ 为\ a\ 倒数,即:b = \frac{1}{a}

但当:

a×b1(modp) b  1a  ()a \times b \equiv 1 \pmod{p} \ 时,b\ 不一定为\ \frac{1}{a} \ \ (因为有取模)

aapp 互质。我们就把 bb 称为 aa 关于 pp 的逆元。记作 a1a^{-1}

例如:

2×3(mod5)12 \times 3 \pmod{5} \equiv 1

那么 33 就是 22 关于 55 的逆元

所以除以一个数再取模等于乘以其逆元再取模,所以逆元又称数论倒数。即:

ab ⁣ ⁣ ⁣ ⁣(modp)=a×b1 ⁣ ⁣ ⁣(modp)\frac{a}{b} \!\!\!\! \pmod{p} = a \times b^{-1} \!\!\! \pmod{p}

求逆元

费马小定理 + 快速幂

对于小于质数 pp 的所有正整数 aa,都有 apa ⁣(modp)a^p \equiv a \!\pmod{p}ap11 ⁣(modp)a^{p-1} \equiv 1 \! \pmod p

推得:

 a×a11(modp)由 \ a \times a^{-1} \equiv 1 \pmod{p}

ap11 ⁣(modp)a^{p-1} \equiv 1 \! \pmod p

 a×a1ap1(modp)得 \ a \times a^{-1} \equiv a^{p-1} \pmod{p}

a1ap2(modp)a^{-1} \equiv a^{p-2} \pmod{p}

可以通过快速幂求出 ap2(modp)a^{p-2} \pmod{p} 的值,就是逆元

ll fpm(ll x, ll power, ll mod) {
    x %= mod;
    ll ans = 1;
    for (; power; power >>= 1, (x *= x) %= mod)
        if(power & 1) (ans *= x) %= mod;
    return ans;
}
int main() {
    ll x = fpm(a, p - 2, p); //x为a在mod p意义下的逆元
}

线性递推

这个适合用于求一连串数字的逆元。

p=k×a+r, (1<r<a<p)    k  pa , r p = k \times a + r,\ (1 < r < a < p)\ \ \ 也就是\ k \ 是\ \frac{p}{a}\ 的商,\ r\ 是余数

变形得:

k×a+r0(modp)k \times a + r \equiv 0 \pmod{p}

两边乘以 a1a^{-1}r1r^{-1} 可得:

k×r1+a10(modp)k \times r^{-1} + a^{-1} \equiv 0 \pmod{p}

a1k×r1(modp)a^{-1} \equiv {-k} \times r^{-1} \pmod{p}

a1pa×(pmoda)1(modp)a^{-1} \equiv -\frac{p}{a} \times (p \bmod{a})^{-1} \pmod{p}

代码如下:

inv[1] = 1;
for(int a = 2; a < p; ++ i)
    inv[a] = (p - p / a) * inv[p % a] % p;  // 加个p是为了保证非负

Java选手

BigIntegermodInverse 直接求逆元:

a.modInverse(p);