1. 首页
2. 模板
3. 本页

乘法逆元模板

条件

对于乘法逆元：在mod m的操作下（即Zm中），a存在乘法逆元当且仅当a与m互质。不定方程ab+mx=1的任意一组整数解(b,x)，b就是a的乘法逆元。具体计算可以使用扩展欧几里德算法(Extended-GCD)。

//******************************
//返回d=gcd(a,b);和对应于等式ax+by=d中的x,y
long long extend_gcd(long long a,long long b,long long &x,long long &y)
{
 if(a==0&&b==0) return -1;//无最大公约数
 if(b==0){x=1;y=0;return a;}
 long long d=extend_gcd(b,a%b,y,x);
 y-=a/b*x;
 return d;
}
//*********求逆元素*******************
//ax = 1(mod n)
long long mod_reverse(long long a,long long n)
{
 long long x,y;
 long long d=extend_gcd(a,n,x,y);
 if(d==1) return (x%n+n)%n;
 else return -1;
}

费马小定理求逆元

//要求mod为素数
LL cal(LL x)
{
    LL res=1;
    int k=mod-2;
    while(k)
    {
        if(k&1)
        {
            res*=x;
            res%=mod;
        }
        x*=x;
        x%=mod;
        k>>=1;
    }
    return res;
}

利用欧拉函数

//mod为素数,而且a和m互质
long long inv(long long a,long long mod)//mod为素数
{
 return pow_m(a,mod-2,mod);
}