求逆元的四种方式

什么是逆元

逆元:在模运算的意义下,如果a*b=1(mod p),则a,b互为对方mod p意义下的逆元.即a=1/b.

一、费马小定理求逆元

费马小定理:若p是质数,则a^(p-1)=1(mod p),即a*a^(p-2)=1(mod p).所以a的逆元为a^(p-2).配合快速幂求解.

注意:该方法只能求p是质数条件下的逆元.

    b=qmi(a,p-2,p);

二、扩展欧几里得求逆元

对于式子 a*b=1(mod p) 可变形为 a*b+p*q=1

其中a是常数,p是常数,故可用扩展欧几里得来求b

int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
........
    int x,y;
    exgcd(a,p,x,y);
    x=(x%p+p)%p;

三、线性求逆元

若需要求出大量的逆元,则可以用这种方式预处理

假设我们要求1~n的逆元

首先inv[1]=1

对于i,我们令p=k*i+r,即k是p/i的商,r是k/i的余数.

在mod 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)

将k和r的意义带入式子:inv[i]=-p/i*inv[p%i]

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

四、线性求阶乘逆元

下面的inv[i]表示i的阶乘的逆元

首先下面式子成立

inv[i]=1/(i!)

inv[i]*i=1/((i-1)!)=inv[i-1]

因此,如果我们要求1~n的阶乘逆元,我们可以先用扩展欧几里得求出n!的逆元,再倒着推回来即可

for(int i=n;i;i--){
    inv[i]=inv[i+1]*(i+1)%p;
}

同时,这种方法也可以求出普通逆元,即i的逆元

我们用invv[i]表示i的逆元

则inv[i]*((i-1)!)=(1/i!)*(i-1)!=1/i=invv[i]

例题 乘法逆元(模板) https://www.luogu.com.cn/problem/P3811