ZOJ 3609 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

Sample Output

4
Not Exist
8

题解：
最小乘法逆元：由ax≡1 (mod m)得：转化为解线性方程ax+by=1
需要注意的地方：最小解取模时不能写成（x%t+t）%t 因为此题要的是正数解 这样写有时会输出0

首先我来回顾下欧几里德的几个定理，有助于理解这道题；

定理一：如果d = gcd(a, b)，则必能找到正的或负的整数k和l，使 d = ax+ by。

定理二：若gcd(a, b) = 1，则方程ax ≡ c (mod b)在[0, b-1]上有唯一解。

定理三：若gcd(a, b) = d，则方程ax ≡ c (mod b)在[0, b/d - 1]上有唯一解。

对于ax+by=1; 即ax=1（mod b）当且仅当gcd（a,b）!=1 的时候，无解！

 1 #include <iostream>  
 2 #include <cstdio>  
 3 #include <cstring>  
 4 #include <cmath>  
 5 #include <vector>  
 6 #include <string>  
 7 #include <queue>  
 8 #include <stack>  
 9 #include <algorithm>  
10 
11 #define INF 0x7fffffff  
12 #define EPS 1e-12  
13 #define MOD 1000000007  
14 #define PI 3.141592653579798  
15 #define N 100000  
16 
17 using namespace std;  
18 
19 typedef long long LL;  
20 typedef double DB;  
21 
22 LL e_gcd(LL a,LL b,LL &x,LL &y)  
23 {  
24     if(b==0)  
25     {  
26         x=1;  
27         y=0;  
28         return a;  
29     }  
30     LL ans=e_gcd(b,a%b,x,y);  
31     LL temp=x;  
32     x=y;  
33     y=temp-a/b*y;  
34     return ans;  
35 }  
36 
37 LL cal(LL a,LL b,LL c)  
38 {  
39     LL x,y;  
40     LL gcd=e_gcd(a,b,x,y);  
41     if(c%gcd!=0) return -1;  
42     x*=c/gcd;  
43     b/=gcd;  
44     if(b<0) b=-b;  
45     LL ans=x%b;  
46     if(ans<=0) ans+=b;  
47     return ans;  
48 }  
49 
50 int main()  
51 {  
52     LL a,b,t;  
53     scanf("%lld",&t);  
54     while(t--)  
55     {  
56         scanf("%lld%lld",&a,&b);  
57         LL ans=cal(a,b,1);  
58         if(ans==-1) printf("Not Exist
");  
59         else printf("%lld
",ans);  
60     }  
61     return 0;  
62 }