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
看代码吧
#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
const int MAXN =1E6;
void exgcd(int a,int b,int &x,int &y,int &d){if(b==0) { d=a; x=1;y=0;}else {exgcd(b,a%b,y,x,d);y-=(a/b)*x;}
}
int chi(int a,int n){int x,y,d;exgcd(a,n,x,y,d);if(d!=1) return -1;x=x%n;if(x<=0) x+=n; return x;
}
int main(){int t;cin>>t;while(t--){int a,m;cin>>a>>m;int ans=chi(a,m);if(ans==-1) puts("Not Exist");else cout<<ans<<endl;}
}