快速幂

leetcode

• 快速幂

普通的幂运算每次只只乘上一次，比如计算pow(2,64)就要循环64次。这样的时间复杂度很高，而快速幂则可以减少运算的复杂度

对于快速幂算法而言，pow(x,y),我们可以把y看成一个二进制数,然后我们以次求出pow(x,1),pow(x,2),pow(x,4),…以此类推，然后我们查看y对应二进制数的每一位，如果为0,则当前数就要乘上x对应二进制的幂。

例如y=13,它对应的二进制数为1101,则pow(x,13)就为pow(x,8)、pow(x,4)、pow(x,1)之和。

• 算法对应的C++代码

int fastpow(int x, int y) 
{
	int ans = 1;
	while (y) 
	{
		if (y & 1) 
		{
			ans *= x;
		}
		x *= x;
	}
	return ans;
}

• 关于取余的一些技巧

  • 加法取余

  (a+b)%c=((a%c)+(b%c))%c

  适合与很多个数相加时，最后的很大，无法存下，就将取余操作放在每次相加后，避免数据过大溢出

  • 乘法取余

  (a*b)%c=((a*c)+(b*c))%c

  同样也是为了避免相乘后数据溢出，就将取余操作放在每次相乘之后