{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://www.xiaopingtou.cn//data/attach/topic/topicKPo7gB.jpg', '推荐 alazhuwang 的文章《逆元的意义及求法》','https://www.xiaopingtou.net/article-53596.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}
快速幂求逆元：
int q_pow(int a,int n,int m) {
int ans = 1;
while(n) {
if (n&1) {
ans = ans*a%m;
}
a = a*a%m;
n >>= 1;
}
return ans;
}
LL Fermatinv(LL a,LL m) { //前提p是质数
return qpow(a,m-2,m);
}
扩展欧几里得求逆元
void ex_gcd(LL a,LL b,LL &x,LL &y){
if(!b){x=1;y=0;return;}
ex_gcd(b,a%b,y,x);
y-=a/b*x;
}
LL mod_rev(LL a,LL n) {
LL x,y;
ex_gcd(a,n,x,y);
return (x+n)%n;
}