Modular Inverse(模逆元，扩展欧几里德)-白红宇

Modular Inverse(模逆元，扩展欧几里德)

阅读量：6278 次

发布时间：2019-06-22

本文共 2237 字，大约阅读时间需要 7 分钟。

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

33 114 125 13

Sample Output

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