1 什么是逆元

如果ax≡1 (mod p),且gcd(a,p)=1(a与p互质)，则称a关于模p的乘法逆元为x。

2 逆元求法①拓展欧几里得(洛谷P1082)

【算法原理】

观察ax≡1 (mod p)，变形为a*x+p*y=1，就可以用扩展欧几里得算法求x了，同时这里也说明了a和p只有在互素的情况下才存在逆元。

【适用范围】

只要存在逆元即可求，适用于个数不多但是mod很大的时候，也是最常见的一种求逆元的方法。

【程序代码】

LL exgcd(LL a,LL b,LL &x,LL &y)//扩展欧几里得算法 
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    LL ret=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return ret;
}
LL getInv(int a,int p)//求a在p下的逆元，不存在逆元返回-1 
{
    LL x,y;
    LL d=exgcd(a,p,x,y);
    return d==1?(x%p+p)%p:-1;
}

3 逆元求法②费马小定理

【算法原理】

若p为素数，则有a^p-1 ≡ 1(mod p)

变换一下：
a^p-2*a ≡ 1(mod p)
a^p-2就是a在mod p意义下的逆元啦。

【适用范围】

一般在p是个素数的时候用，比拓展欧几里得快一点而且好写。（但仅限素数）

LL qkpow(LL a,LL p,LL mod)
{
    LL t=1,tt=a%mod;
    while(p)
    {
        if(p&1)t=t*tt%mod;
        tt=tt*tt%mod;
        p>>=1;
    }
    return t;
}
LL getInv(LL a,LL p)
{
    return qkpow(a,p-2,p);
}

4 逆元求法③递推求逆元(洛谷P3811)

【算法原理】

(这里准备好草稿纸嗷)

p是模数，i是待求的逆元，我们现在要求i在mod p意义下的逆元 i^-1

即：i*x+r ≡ 1 (mod p)

首先，当i＝1时，i^-1＝1

当2≤i＜p时，i*i^-1 ≡ 1 (mod p)

令,则p = k*i+r

k∗i+r ≡ 0 (modp)

式子两边同乘r⁻¹，i⁻¹，因为r*r⁻¹ ≡ 1 (mod p)  , i*i⁻¹ ≡ 1 (mod p)

因此k∗r⁻¹+i⁻¹ ≡ 0 (mod p)

i⁻¹ ≡ −k*r⁻¹ (mod p)

i⁻¹ ≡ −p/i*inv[p mod i]

公式有点丑，说白了就是:

inv[1]=1

inv[i] = -(p/i)*inv[i%p]

【适用范围】求一连串的数字的逆元时非常使用，但要保证i<p

【顺序实现】

LL inv[mod+5];
void getInv(LL mod)
{
    inv[1]=1;
    for(int i=2;i<mod;i++)
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}

【递归实现】

在此基础上我们用递归写程序，可以用来求不连续的数字的逆元

LL inv(LL i)
{
    if(i==1)return 1;
    return (p-p/i)*inv(p%i)%p;
}

这个就是求逆元最简单的算法了！！