#include <iostream>
using namespace std;
int main() {
int q;
cin>>q;
while(q--){
long long a,b,p;
cin>>a>>b>>p;
long long result=1;
while(b){
if(b&1){
result=result*a%p;
}
b>>=1;
a=a*a%p;
}
cout<<result<<endl;
}
return 0;
}
快速幂是快速计算底数的n次幂,其时间复杂度为O(log n),与朴素的O(N)相比极大地提高了效率。
例如计算
,11的二进制是1011,即
,
因此
。
版权声明:本文为qq_45122293原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。