求逆元模板题,直接抄袭了yimao哥的模板
注意m=1时的特殊情况即可。
#include <cstdio> #include <iostream> using namespace std; int ext_gcd(int a,int b,int &x,int &y){ if(!b) {x=1,y=0;return a;} int d=ext_gcd(b,a%b,y,x); y-=a/b*x; return d; } int Inv(int a,int m){ int d,x,y; d=ext_gcd(a,m,x,y); if(1!=d) return -1;//gcd(a,b)!=1此时无解 else return (x%m+m)%m; } int main() { int T,a,m; cin>>T; while(T--) { cin>>a>>m; if(m==1){ puts("1"); continue; } int d=Inv(a,m); if(-1==d) puts("Not Exist"); else cout<<d<<endl; } return 0; }