求逆元

2023/6/26 C++ 算法竞赛 数论 逆元

一般求逆元有三种方法：扩欧、快速幂、递推

扩展欧几里得求逆元

等价于

由扩展欧几里得解丢番图方程可以得到逆元

ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0){x=1;y=0;return a;}
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
ll mod_inverse(ll a,ll m)
{
    ll x,y;
    exgcd(a,m,x,y);
    return (x%m+m)%m;
}

快速幂求逆元

由费马小定理， 就是 在模 意义下的逆元

ll mod_inverse(ll a,ll m)
{
    return fast_pow(a,m-2,m);
}

递推求逆元

对于 ，设

有 , 即 

int inv[N];
void mod_inverse(ll n,ll p)
{
    inv[1]=1;
    for(int i=2;i<=n;i++)
    {
        inv[i]=(ll)(p-p/i)*inv[p%i]%p;
    }
}
img_show