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.
<h4< dd="">Output
For each test case, output the smallest positive x. If such x doesn't exist, output "Not Exist".
<h4< dd="">Sample Input
3
3 11
4 12
5 13
<h4< dd="">Sample Output
4
Not Exist
8 这题就是求乘法逆元
我用的方法比较复杂，我是这么想的，先判断a和f是不是互质，如果互质才有乘法逆元，否则没有乘法逆元，费马小定理可以求出膜是素数的乘法逆元，欧拉定理可以求出膜是非素数的乘法逆元：
具体方法：费马小定理，先要判断是不是素数，然后再用快速幂
欧拉定理，先要写欧拉函数，然后再用快速幂，其中欧拉函数需要一个质数的数组isp
所以用这种方法要写很多的函数，不过也好，昨天学的，正好好好的复习一下
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
typedef long long ll;
const int maxn=1e5;
int p[maxn];//素数筛
void init()
{
for(int i=2;i<maxn;i++) p[i]=1;
for(int i=2;i*i<maxn;i++)
{
if(p[i])
{
for(int j=i*i;j<maxn;j+=i)
{
p[j]=0;
}
}
}
}
//v数组记录每一个i的最小质因数，isp记录所有的质数
int v[maxn],isp[maxn],m;
void init1()
{
for(int i=2;i<maxn;i++)
{
if(v[i]==0)
{
isp[m++]=i;
v[i]=i;
}
for(int j=0;j<m;j++)
{
if(v[i]<isp[j]||i*isp[j]>maxn) break;
v[i*isp[j]]=isp[j];
}
}
} int gcd(int a,int b)
{
return b==0? a:gcd(b,a%b);
}
int euler(int n)
{
int res=n;
for(int i=0;i<m;i++)
{
if(n%isp[i]==0)
{
res=res*(isp[i]-1)/isp[i];
}
}
return res;
}
int mod;
ll mod_pow(ll x,int n)
{
ll ans=1;
while(n)
{
if(n & 1) ans=ans*x%mod;
x=x*x%mod;
n>>=1;
}
return ans;
} int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int f;
ll a;
scanf("%I64d%d",&a,&f);
init();
init1();
mod=f;
int ans;
if(gcd(a,f)==1)
{ if(p[f])//费马小定理
{
ans=mod_pow(a,f-2);
}
else//欧拉定理
{
int exa=euler(f);
ans=mod_pow(a,exa-1);
}
}
else {
printf("Not Exist\n");
continue;
}
printf("%d\n",ans);
}
return 0;
}