逆元
(逆元) $O(nlogp)$
时间复杂度
nlogp
C++ 代码
#include <iostream>
using namespace std;
long long getQuickPow(int a, int b, int c)
{
long long res = 1;
long long temp = a;
while(b)
{
int t = b & 1;
if(t) res = res * temp % c;
temp = temp * temp % c; // 这个temp也会越界的
b = b >> 1;
}
return res;
}
bool ishz(int a, int b)
{
if(a % b == 0) return false;
return true;
}
// 个人感觉这个知识点没有什么卵用,不过记住互质的两个数逆元为b^(p-2)就行了
int main()
{
int n;
cin >> n;
while(n--)
{
int b, p;
cin >> b >> p;
if(ishz(b, p)) cout << getQuickPow(b, p - 2, p) << endl;
else cout << "impossible" << endl;
}
}