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
题解：求最小正整数解，其实吧，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<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 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<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
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;
}