1.逆元(Inverse element)
定义:对于正整数a和m,如果有a⋅x≡1(mod m),那么把这个同余方程中x的最小正整数解叫做a模m的逆元。
应用:当计算(a/b)% m时不能直接算(double)%(int),要转化成(a*c)%m,其中c是b的逆元
证明如下:
设c是b的逆元,则有b*c≡1(mod m);
则(a/b)%m = (a/b)*1%m = (a/b)*b*c%m = a*c(mod m);
即a/b的模等于a*(b的逆元)的模;
奇技淫巧:
2.逆元的求解方法---b*c≡1(mod m),b,m已知,求c
注意:b和m只有值互质的情况下才存在逆元
(1)扩展欧几里得算法(O(log b))-----适用条件:存在逆元即可
typedef long long ll;
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 mod)//求a在mod下的逆元,不存在逆元返回-1
{
ll x,y;
ll d=exgcd(a,mod,x,y);
return d==1?(x%mod+mod)%mod:-1;
}
(2)费马小定理(O(log m))-----存在逆元且m是素数
typedef long long ll;
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 mod)
{
return qkpow(a,mod-2,mod);
}
[参考博客]:
https://blog.csdn.net/xiaoming_p/article/details/79644386
https://blog.csdn.net/slongle_amazing/article/details/50669001