[C++知识库]数学知识：快速幂

求

先把k换算成二进制形式，可以变成

例如?=??=?

这样能极大的减少时间复杂度

例题：

?代码：

#include<stdio.h>

typedef long long LL;

int solve(int a,int k,int p)
{
	int ans=1;
	while(k)
	{
		if(k&1)//如果k的二进制的最后一位是1,进行计算  
			ans=(LL)ans*a%p;
		k>>=1;//删除k的末尾(二进制的末尾) 
		a=(LL)a*a%p; 
	}
	return ans;
}

int main()
{
	int n;
	scanf("%d",&n);
	while(n--)
	{
		int a,k,p;
		scanf("%d%d%d",&a,&k,&p);
		printf("%d\n",solve(a,k,p));
	}
	return 0;
}