Modular Inverse

---

Time Limit: 2 Seconds      Memory Limit: 65536 KB

---

The modular modular multiplicative inverse of an integer a modulo m is an integer x such that a-1≡x (mod m). This is equivalent to ax≡1 (mod m).

Input

There are multiple test cases. The first line of input is an integer T ≈ 2000 indicating the number of test cases. Each test case contains two integers 0 < a ≤ 1000 and 0 < m ≤ 1000.

Output

For each test case, output the smallest positive x. If such x doesn't exist, output "Not Exist".

Sample Input

3 3 11 4 12 5 13

Sample Output

4 Not Exist 8
题解：求最小正整数解，其实吧，x的通解是x0+b/gcd*t，由于t是整数，那么ans=x0+b/gcd*t=x0 mod b=x0%b；因为ans要是正整数的，
所以当b/gcd是负的时候，就等于绝对值就好了，因为还有t啊，当x0%b负时,加上一个b；就妥了；因为ans=(x0+b)%b;
代码： 1 #include 2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int INF=0x3f3f3f3f; 8 typedef long long LL; 9 void e_gcd(LL a,LL b,LL &d,LL &x,LL &y){ 10 if(!b){ 11 d=a; 12 x=1; 13 y=0; 14 } 15 else{ 16 e_gcd(b,a%b,d,x,y); 17 LL temp=x; 18 x=y; 19 y=temp-a/b*y; 20 } 21 } 22 LL cal(int a,int b,int c){ 23 LL x,y,d; 24 e_gcd(a,b,d,x,y); 25 if(c%d!=0)return -1;//ax+by=c/(c/gcd); 26 x*=c/d; 27 b/=d;//因为x的通解是x0+(b/gcd)t; 28 if(b<0)b=-b; 29 LL ans=x%b; 30 if(ans<=0)ans+=b; 31 return ans; 32 } 33 int main(){ 34 LL T,a,b,d,x,y; 35 scanf("%d",&T); 36 while(T--){ 37 scanf("%lld%lld",&a,&b); 38 LL ans=cal(a,b,1); 39 if(ans==-1)puts("Not Exist"); 40 else printf("%lld ",ans); 41 } 42 return 0; 43 }  题上数据比较水，数据范围1000，暴力一下就可以了： #include #include #include #include #include using namespace std; const int INF=0x3f3f3f3f; typedef long long LL; int main(){ int T,a,m; scanf("%d",&T); while(T--){//(1-ax)%m; scanf("%d%d",&a,&m); int flot=0; for(int x=1;x<=1000;x++){ if((1-a*x)%m==0){ flot=1; printf("%d ",x); break; } } if(flot)continue; puts("Not Exist"); } return 0; }