【模板】二分求幂求a的b次方

最新推荐文章于 2025-04-01 09:47:31 发布

coderwait

最新推荐文章于 2025-04-01 09:47:31 发布

阅读量204

点赞数

分类专栏：算法理论和模板

本文链接：https://blog.csdn.net/coderwait/article/details/89460230

版权

算法理论和模板专栏收录该内容

31 篇文章

订阅专栏

思想

二分方法降低求幂问题的时间复杂度。

以2的31次方为例：

$2^{31}=2^{16}2^{8}2^{4}2^{2}2^{1}$

而 $2^{2}$ 可以由 $2^{1}$ 得到， $2^{4}$ 可以由 $2^{2}$ 得到。

我们的目标就是将 $a^{b}$ 分解成若干个 $a$ 的 $2^{k}$ 的积，并尽可能减少分解结果的个数。这就是二进制数分解。

$31=2^{4}+2^{3}+2^{2}+2^{1}+2^{0}=(11111)_{2}$

循环次数	a(下一位的权重)	b(当前待分解)	ans
0	$2^{1}$	31	1
1	$2^{2}$	15	$2^{1}$
2	$2^{4}$	7	$2^{3}$
3	$2^{8}$	3	$2^{7}$
4	$2^{16}$	1	$2^{15}$
5	$2^{32}$	0	$2^{31}$

#include<iostream>
using namespace std;
int main(void)
{
	int a,b;//求a的b次方
	while(cin>>a>>b){
		if(a==0&&b==0) break;
		int ans = 1;//保存最终结果 
		while(b!=0){//若b不是0，说明二进制转换没有结束 
			if(b%2==1){
			//如果当前二进制位是1，需要累乘a的2^k次方到ans中
			//其中2^k是当前二进制位的权重 
				ans = ans*a;
				ans = ans % 1000;
			}
			b=b/2;
			a = a*a;//求下一位二进制的权重，a求平方
			//依次是2^1,2^2,2^4 
			a = a%1000;
		}
		cout<<ans<<endl;
	} 
	return 0;
 }