【算法竞赛】数学专题：02.快速幂运算

本文主要是介绍【算法竞赛】数学专题：02.快速幂运算，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1.通过递归实现快速幂运算：

int power(int a, int n)
{
	int ans;
	if (n == 0)//结束条件
		ans = 1;
	else
	{
		ans = power(a * a, n / 2);//递归调用
		if (n % 2 == 1)//若 n 为奇数，ans 需再乘一个 a。
			ans *= a;
	}
	return ans;
}

注：书写递归时需要先写特殊情况（出口）。

2.通过循环实现快速幂运算：

int power(int a, int n)
{
	int ans = 1;
	while (n)//当 n 不为 0 时
	{
		if (n % 2)//若 n 为奇数
			ans *= a;
		a = a * a;//底数平方
		n /= 2;//指数减半
	}
	return ans;
}

3.算法竞赛中，几乎所有的快速幂在运算时，所有的乘法都要取模。如：

int power(int a, int n)
{
	int ans = 1;
	while (n)//当 n 不为 0 时
	{
		if (n % 2)//若 n 为奇数
			ans = ans * a % MOD;
		a = a * a % MOD;//底数平方
		n /= 2;//指数减半
	}
	return ans;
}

4.快速幂运算的时间复杂度为O（logN）.

这篇关于【算法竞赛】数学专题：02.快速幂运算的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！