逆元与求解
学习笔记
逆元
当 \(ax\equiv1\ (mod \ b)\) 称 \(x\) 为 \(a \mod b\) 的逆元，记作 \(a^{-1}\)。
拓展欧几里得法
快速幂法
因为 \(ax \equiv1\ (mod\ b)\)
所以 \(ax \equiv a^{b-1}\ (mod\ b)\) （费马小定理）
所以 \(x \equiv a^{b-2}\ (mod\ b)\)
此时直接快速幂模 \(b\) 即可。
时间复杂度 \(O(a⋅logb)\)
非常简单还要看吗？
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=10005;
ll a,b;
ll quickpow(ll x,ll k,ll mod){
ll sum=1;
while(k){
if(k&1){
sum*=x;
sum=(sum+mod)%mod;
}
x*=x;
x=(x+mod)%mod;
k>>=1;
}
return sum;
}
int main(){
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--){
cin>>a>>b;
if(a%b==0){//并不互质，不合法
cout<<"impossible\n";
}
else{
cout<<quickpow(a,b-2,b)<<"\n";
}
}
return 0;
}