J - Modular Inverse
ZOJ - 3609
The modular modular multiplicative inverse of an integer a modulo m is an integer xsuch 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
代码语言：javascript复制3
3 11
4 12
5 13Sample Output
代码语言：javascript复制4
Not Exist
8&：1 的逆元就是 1。
代码语言：javascript复制//#include <bits/stdc .h>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <iostream>
#define rep(i,a,b) for(int i = (a); i < (b); i )
#define per(i,a,b) for(int i = (a); i > (b); i --)
#define MM(a) memset(a,0,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll maxn = 300;
const ll mod = 1e9 7;
ll extend_gcd(ll a, ll b, ll &x, ll &y)
{
if(b==0)
{
x=1ll;
y=0;
return a;
}
else
{
ll r = extend_gcd(b,a%b,y,x);
y-=x*(a/b);
return r;
}
}
vector<ll>line_mod(ll a,ll b,ll n)
{
ll x,y;
ll d=extend_gcd(a,n,x,y);
vector<ll>ans;
ans.clear();
if(b%d==0)
{
x%=n;
x =n;
x%=n;
ans.push_back(x*(b/d)%(n/d));
for(ll i=1; i<d; i)
{
ans.push_back((ans[0] i*n/d)%n);
}
}
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
ll a,m;
scanf("%lld %lld",&a,&m);
vector<ll>ans = line_mod(a,1ll,m);
sort(ans.begin(), ans.end());
if(ans.empty())printf("Not Existn");
else if(ans[0] == 0) printf("1n");
else printf("%lldn",ans[0]);
}
return 0;
}
