快速幂

定义

快速幂是一种计算aⁿ时，将n表示成2进制进行计算，减少乘法次数的快速计算幂的方法。时间复杂度为O(logn)。
例： 3¹³ = 3¹¹⁰¹=3⁸3⁴3¹。

实现

递归实现

迭代实现

不取模

int fast_pow(int a,int b)
{
	int result = 1;
	while(b > 0)
	{
		if(b & 1)
			result *= a;
		a *= a;
		b >>= 1;
	}
	return result;
}

取模

const int MOD = 9901;
int fast_pow(int a,int b)
{
	a %= MOD;
	int result = 1;
	while(b > 0)
	{
		if(b & 1)
			result = result * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return result;
}