题目描述
给定 n 组 ai,pi,其中 pi 是质数,求 ai 模 pi 的乘法逆元,若逆元不存在则输出 impossible。
注意:请返回在 0∼p−1 之间的逆元。
乘法逆元的定义
若整数 b,m 互质,并且对于任意的整数 a,如果满足 b|a,则存在一个整数 x,使得 a/b≡a×x(modm),则称 x 为 b 的模 m 乘法逆元,记为 b−1(modm)。
b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时,bm−2 即为 b 的乘法逆元。
#include<bits/stdc++.h>
using namespace std;
int fast(int a,int k,int p){
int ans=1;
while(k){
if(k&1)
ans=(long long)ans*a%p;
k>>=1;
a=(long long)a*a%p;
}
return ans;
}
int main(){
int n;
cin>>n;
while(n--){
int a,p;
cin>>a>>p;
if(a%p==0)
cout<<"impossible"<<endl;
else{
int ans=fast(a,p-2,p);
cout<<ans<<endl;
}
}
return 0;
}