题目描述
快速幂:要求a^k,可以利用k的二进制形式进行拆分,累次平方求出a^k;
C++ 代码
#include<iostream>
using namespace std;
typedef long long LL;
LL qmi(int a,int k,int p)
{
LL res=1;
while(k)
{
if(k&1) res=res*a%p;//将k写成二进制形式,不断对结果进行累加。
k>>=1;
a=(LL)a*a%p;
}
return res;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int a,p,k;
scanf("%d %d %d",&a,&k,&p);
printf("%lld\n",qmi(a,k,p));
}
return 0;
}