ZOJ 3609 Modular Inverse 解线性模方程

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

模线性方程ax=b (mod n)，令d=exgcd(a,n),该方程有解的充要条件为 d | b ，即 b% d==0

方程ax=b(mod n)的最小解 :x=(x*(b/d))%n

方程ax=b(mod n)的最整数小解: x=(x%(n/d)+n/d)%(n/d)

//0ms	168k
#include
  
   
#include
   
     int exgcd(int A,int &x,int B,int &y) { int x1,y1,x0,y0; x0=1;y0=0; x1=0;y1=1; int r=(A%B+B)%B; int q=(A-r)/B; x=0;y=1; while(r) { x=x0-q*x1; y=y0-q*y1; x0=x1; y0=y1; x1=x;y1=y; A=B;B=r;r=A%B; q=(A-r)/B; } return B; } int main() { int t; scanf("%d",&t); while(t--) { int a,b=1,n,x,y; scanf("%d%d",&a,&n); int d=exgcd(a,x,n,y); if(b%d==0) { x=(x%(n/d)+n/d)%(n/d); if(!x)x++; printf("%d\n",x); } else printf("Not Exist\n"); } }