ZOJ3609 Modular Inverse(扩展欧几里得)

 

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

References

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

---

Author: WU, Zejun Contest: The 9th Zhejiang Provincial Collegiate Programming Contest

 

 

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3609

 

 

思路：如果a*x + m * y = 1 即gcd(a,m）= 1 则说明x是a的逆元，否则不是。

又因x可能是负数，所以要提前判断下。

代码如下：

 

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int t; int exgcd(int a, int b, int &x, int &y){ if(b == 0){ x = 1; y = 0; return a; } int r = exgcd(b,a%b,y,x); y -= a/b * x; return r; } int main(){ scanf("%d",&t); while(t --){ int a,m; scanf("%d%d",&a,&m); int x,y; int d = exgcd(a,m,x,y); if(d != 1) printf("Not Exist\n"); else{ while(x <= 0) x += m; printf("%d\n",x); } } return 0; }