题目描述
blablabla
样例
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll b,p,n;
ll mod(ll a,ll n,ll k)
{
if(n==0) return 1;//0次方乘法==1,逆元==1
if(n==1) return a%k;//特判一次方
ll y=mod(a,n/2,k);
if(n%2==0) return y*y%k;//两种情况;奇偶
else return (((y*y)%k)*a)%k;
}
int main()
{
cin>>n;
while(n--)
{
cin>>b>>p;
if(b%p==0) cout<<"impossible"<<endl;//不互质,没有逆元
else cout<<mod(b,p-2,p)<<endl;//欧拉定理->费马小定理:b,p互质时欧(b)mod n同余1,当p为质数时,O(p)=n-1;
//b的p-2次方是b mod p的乘法逆元
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla