快速幂

原理

一个数 k 均可以转换为二进制

如10 (10)= 1010 (2)

即10 = 2 + 8=2^1+2^3

经一般化处理可看出对于整数 a , b

有 a^b=a^x[0]+a^x[1]+a^[2]+···

如此可以大量减少乘法操作

代码实现

long long pow(long long a,long long b,long long p)	//a^b (mod p)
{
	long long ans=1;
	a%=p;//如果 a 大于 p，则必须进行取模
	for(; b; b>>=1)
	{
		if(b&1==1)	//此位为1 
        	ans*=(A%p);
		A=(A*A)%p;
	}
	return ans;
}