ZOJ——3609 Modular Inverse（逆元）

The modular modular multiplicative inverse of an integer a modulo m is an integer xsuch 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

Sample Output

4
Not Exist
8

References

http://en.wikipedia.org/wiki/Modular_inverse

题意：英语不好没关系，看它叫我们求什么，它叫我们求最小的x 然后x满足ax≡1 (mod m).，理解到这儿就可以了。

题解：ax≡1 (mod m) 等价于 ax % m = 1 ,求x的最小值，记住这个式子我们可以化为 ax-my=1;所以用到欧几里得，既然为欧几里得那么式子可以写成 ax+my=1 (利用欧几里得的时候加减无所谓，本人小理解)，ax≡1 (mod m) 中x表示a的逆元，求逆元需要gcd(a,m)=1,如果不等于一则无解。如果等于一，则可以求解，详细过程请看代码。

#include <iostream>
using namespace std;
int ex_gcd(int a,int b,int &x,int &y){ // 求ax+by=1的逆元和gcd(a,b)
	if(b==0){
		x=1,y=0;
		return a;
	}
	int q=ex_gcd(b,a%b,y,x);
	y-=a/b*x;
	return q;
}
int main(){
	int n;
	cin >> n;
	while(n--){
		int a,b;
		int x,y;
        cin >> a >> b;
		int z=ex_gcd(a,b,x,y);
		if(z!=1){ // gcd(a,b)!=1 说明无解
			cout << "Not Exist" << endl;
			continue;
		}
		int ans=x;//x为a的逆元
		ans%=b;//求最小逆元需要mod一下b
		if(ans<=0){// 求最小逆元的过程
			ans+=b;
		}
		cout << ans << endl;// 输出最小逆元
	}
	return 0;
}