算法学习-数论专题-乘法逆元

概述

乘法逆元定义：如果一个线性同余方程$ax\equiv 1 \mod b$，则$x$成为$a \mod b$的逆元，记作$a^{-1}$。

乘法逆元一般用于求$a/b\mod p$的值（$p$通常为质数），是解决模意义下分数数值的必要手段。

对于$a/b\mod p$，我们可以求出$b$在$\mod p$下的逆元，然后乘上$a$再$\mod p$，就是这个分数的值了。

求解逆元的方法

扩展欧几里得法

求解$ax\equiv 1 \mod b$ 等价于解不定方程 $ax+by=1$，求解出的$x$即为$a \mod b$的逆元。

1
2
3
4
5
6
7
8

void exgcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

快速幂法

费马小定理

若$p$为质数，$a$为正整数，且$a$、$p$互质，则$a^{p-1}\equiv 1 (\mod p)$。

因为$ax\equiv 1\mod b$

所以$ax\equiv a^{b-1}\mod b$

所以$x\equiv a^{b-2}\mod b$

然后可以使用快速幂求解逆元。

代码略。

线性求逆元

假设现在要求$inv[i]$。

考虑带余除法，设$p=iq+r$，则有$iq+r\equiv 0\mod p$

注意到$p$是质数，因此$r$不为$0$，$r$的逆元存在

等式两边乘$i^{-1}r^{-1}$，得到$qr^{-1}+i^{-1}\equiv 0\mod p$

因此$i^{-1}\equiv -qr^{-1}\equiv -(p/i)(p \mod i)^{-1}\mod p$

1
2

for (inv[1] = 1, i = 2; i <= n; ++i)
    inv[i] = (p - p / i) * inv[p % i] % p;