快速幂
(快速幂) $O(mlogn)$
时间复杂度
mlogn
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;
}
int main()
{
int n;
cin >> n;
while(n--)
{
int a, b, c;
cin >> a >> b >> c;
cout << getQuickPow(a, b, c) << endl;
}
return 0;
}