假设有题目(A/B)%mod,但是数据很大的时候,不好计算或者题目没有直接给A,就可以用逆元
因为是不存在(A%mod /B%mod)%mod的,所有引入逆元;
求A的逆元X:A*X=1%mod;
方法一:如果mod是一个质数,可以用快速幂求,X=pow(A,mod-2,mod);
ll niyuan(ll a,ll b,ll mod)
{
ll r=1,ans=a;
while(b)
{
if(b&a) r=(r*ans)%mod;
ans=(ans*ans)%mod;
b>>=1;
}
return r;
}
方法二:欧几里得求逆元
ll gcd(ll a,ll b,ll &d,ll& x,ll& y){
if(!b){
d=a;
x=1;
y=0;
return x;
}
else{
gcd(b,a%b,d,y,x);
y-=x*(a/b);
}
if(d!=1) return -1;//不存在;
while(x<0) x+=b;
return x;
}