快速幂

快速幂

要计算(a^b)常规方法要进行b次循环，时间复杂度过高，而快速幂就是将幂运算时间复杂度将缩减到(log_2 b)
以(7^9)为例，9的二进制表示为1001，(7^9=7^8*7^1),那么(a^b)就可以表示为(a^i)(0<=i<= b && b的二进制数从右到左第（(log_2 i) +1）位为1的累乘。

代码实现，用一个p存取当前用来累乘的值，每循环一次p自乘一次，b不断右移实现判断从右到左第（(log_2 i) +1）位是否为1。

无取模

int quickPower(int a,int b)
{
	int ans=1, p=a;
	while(b>0)
        {
	      if(b&1)
	      ans*=p;	
              p*=p;
	      b >>= 1;
	}
	return ans;
}

含取模运算

int quickPower(int a,int b,int m)
{
	int ans=1, p=a;
	while(b>0)
        {
	      if(b&1)
	      {
	            ans*=p;
	            ans%=m;
	      }		
              p*=p;
              p%=m;
	      b>>=1;
	}
        ans%=m;
	return ans;
}