转载

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
题解：求最小正整数解，其实吧，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/n",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/n",x); break; } } if(flot)continue; puts("Not Exist"); } return 0; }

正文到此结束