C++快速幂

快速幂的作用：

当我们做一些高次幂的计算时，就不能直接进行暴力的计算。例如：需要计算2^n

并且n≤10^18。这时候如果我们直接进行暴力的计算，时间复杂度为O ( n )，那么肯定会超时，这时候我们就需要一些更优美的算法来帮我们解决这个问题。

快速幂的思路：

首先我们要明确一点，对于一个m^n，当n为偶数时m^n= (m^2 )^n/2

如果知道了这一点我们的问题就迎刃而解了。

求解x^k。

定义：x为当前的底数，f为临时存放处。

当k为偶数时，x*= x , k / = 2

当k为奇数时，k−− , f*= x，然后再以k为偶数的情况进行计算。

代码实现：

int quickpow(int n,int k) {

	long long x=n,f=1;

	while(k>1) {

		if(k%2==1){

 	k--;

    f*=x;

}

		x*=x;

        k/=2;

	}

	return x*f;

}

巴特西

C++快速幂

C++快速幂

快速幂的作用：

快速幂的思路：

代码实现：

最新文章

热门文章