扩展欧几里得求逆元(模数可以不为质数)

LL ex_gcd(LL a,LL b,LL &x,LL &y) {if(b==0){x=1;y=0;return a;}LL ans=ex_gcd(b,a%b,y,x);y-=a/b*x;return ans; }LL inverse(LL a,LL n) {LL d,x,y;d=ex_gcd(a,n,x,y);return d==1?(x+n)%n:-1; }

 

总结

以上是生活随笔为你收集整理的扩展欧几里得求逆元(模数可以不为质数)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。