乘法逆元小结

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

逆元定义

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

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

a⊥m(即 am 互质)时,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} \rfloorkp \bmod ir


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 ;
分类: 数论

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注