引言

所谓快速幂是指快速求得a的b次方的方法。求a^b,最朴素的想法便是不断进行b次累乘,但真的需要进行b次乘法运算吗?

分析

假如要计算2^32,当求得2^16次方之后,可以直接对2^16进行平方得到2^32,并不需要在2^16基础上再进行16次累乘。

相应地,求2^16只需对2^8求平方即可。同理,求2^8,只需对2^4平方……以此类推。

例如求3^29等价于求$3^1 * 3^4 * 3^8 * 3^{16}$

那么1,4,8,16是怎么算出来的呢?

29的二进制表示为11101

所以$29=2^4+2^3+2^2+2^0=16+8+4+1 $

这样就确定了3的哪些次幂是要进行累乘的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
using namespace std;

// 求快速幂
int QuickPower(int x,int n){
int answer = 1;
while (n != 0) {
if (n % 2 == 1) {
answer *= x;
}
n /= 2;
x *= x;
}
return answer;
}
int main(){
int a,b;
printf("%d\n", QuickPower(a, b));
return 0;
}

__END__

三国小梦
文章作者:三国小梦
文章出处使用c++求快速幂
作者签名:简单地活着, 肆意又精彩.
关于主题Hexo - Live For Code
版权声明:文章除特别声明外,均采用 BY-NC-SA 许可协议,转载请注明出处