Java教程

【算法竞赛】数学专题: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.快速幂运算的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!