乘法逆元小结

乘法逆元在算法竞赛中具有十分重要的应用。

逆元定义

对于正整数 a 和 m ，如果有 ax\equiv 1\pmod{m} ，那么把同余方程中 x 的最小正整数解叫做 a 模 m 的逆元，记作a^{-1}，也可以称 x 为 a 在模 m 意义下的倒数。

所以对于 \frac{a}{b} \pmod p ，我们可以求出 b 模 p 的逆元，然后乘以 a ，就可以算出结果了。

当a⊥m（即 a 与 m 互质）时，a 在模 m 意义下存在逆元。

以下介绍求逆元的几种方法，每种方法均应理解并掌握。

扩展欧几里得求解逆元

因为需要解 ax\equiv1 \pmod m，即
ax+my =1
的 x 的最小正整数解

直接用扩欧即可

该方法不要求 m 为质数

void exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) x = 1, y = 0;
    else exgcd(b, a % b, y, x), y -= a / b * x;
}
int main() {
    ll x, y;
    exgcd (a, p, x, y);
    x = (x % p + p) % p;
    printf ("%d\n", x); //x是a在mod p下的逆元
}

利用费马小定理求解逆元

费马小定理(Fermat’s little theorem)是数论中的一个重要定理，在1636年提出。如果 p 是一个质数，而整数 a 不是 p 的倍数，则有
a^{p-1}≡1 \pmod p

解 ax\equiv1 \pmod m，此方法要求 m 为质数。

因为有
a^{m-1}\equiv1 \pmod m
所以知道
a*a^{m-2}\equiv1 \pmod m
故
x=a^{m-2}
利用快速幂求得即可。

线性递推求逆元

首先有 1 关于 m 的逆元为 1 ，即 1^{-1}\equiv1 \pmod m

然后对于数 i ，有
p=\lfloor \frac{p}{i} \rfloor *i +p\bmod i
我们记 \lfloor \frac{p}{i} \rfloor 为 k ，p \bmod i 为 r

有
k_i+r \equiv0 \pmod p
等式两边同乘 i^{-1} 和 r^{-1} ，得
k_r^{-1}+i^{-1}\equiv0 \pmod p

于是有
i^{-1}\equiv-k*r^{-1}\pmod p
就可以递推出 i 的逆元了

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

考虑到逆元取正数，一般写成

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