乘法逆元的几种求法

unique✔ · 2020-03-13 15:42:39 · 个人记录

知乎乘法逆元

博客园乘法逆元多了阶乘方法

一·扩展欧几里得算法

已知a,b，找到x,y使它们满足贝祖等式：ax+by=gcd(a,b);
首先因为b不等于0，gcd(a,b)=gcd(b,a ~mod~b)

如果有一组解x',y'使得

bx'+(a ~mod ~b)y'=gcd(b,a ~mod ~b)

那么

ax+by=bx'+(a~ mod ~b)y'

因为 a~ mod ~b =a - [a/b]b

所以：

ax+by = bx'+(a-[a/b]b)y'

变形

ax+by = ay'+b(x'-[a/b]y')

然后就得到一组特解： x=y; y=x'-[a/b]y'

上面的过程不断的递归下取，一直到b=0为止，此时表达式为

ax+0y=gccd(a,0) x=1;y=0;

代码

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;//注意x可能为负数
    cout << x << endl;
    return 0;
}

二·快速幂费马小定理

费马小定理：如果p为素数，a为正整数且a,p互质，那么a^{p-1}=1(modp)

那么可以提一个a出来，它是要求乘法逆元的数；

a*a^{p-2}=1(modp)

所以a的乘法逆元就是a^{p-2}，用快速幂求

代码

inline ll qpow(ll a, ll n, ll p)// 快速幂
{
    ll ans = 1;
    while (n)
    {
        if (n & 1)
            ans = ans % p * a % p;
        a = a % p * a % p;
        n >>= 1;
    }
    return ans;
}
inline ll inv(ll a, ll p)
{
    return qpow(a, p - 2, p);
}

三·线性算法（对于求一连串的乘法逆元）

首先1的乘法逆元是1

设p=k*i+r,(1<r<i<p) ,k=p/i,r=p ~mod ~i

将式子放在(mod ~p)意义下

p=k*i+r=0(mod ~p)

两边乘上i^{-1},r^{-1}得

k*r^{-1}+i^{-1}=0(mod ~p)

i^{-1}=-k*r^{-1}(mod ~p)

i^{-1}=-[p/i]*(p ~mod ~i)^{-1}(mod ~p)

代码

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