\(O(n\log_2b)\)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n, a, b, p;
int qp(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = (ll)res * a % p;
a = (ll)a * a % p;
b >>= 1;
}
return res;
}
int main() {
cin >> n;
while (n--) {
cin >> a >> b >> p;
cout << qp(a, b, p) << endl;
}
return 0;
}
这题有个很强的性质 \(p\) 是质数。
根据费马小定理 \(b^{p-1}\equiv 1\pmod p\)
\(b^{-1}x\equiv 1\pmod p\)
我们要求出 \(x\)。
\[\begin{aligned}b^{p-1}&\equiv1\pmod p\\b\cdot b^{p-2}&\equiv \pmod p \end{aligned}
\]
所以 \(x=b^{p-2}\)
证毕