本词条缺少信息栏、名片图，补充相关内容使词条更完整，还能快速升级，赶紧来吧！
快速幂顾名思义，就是快速算某个数的多少次幂。其时间复杂度为 O(log?N)， 与朴素的O(N)相比效率有了极大的提高。
目录
1
原理2
实现3
代码比较常规求幂二分求幂（一般）快速求幂（位操作）快速求幂（位运算，与pow3函数的实际行为相同，但看起来复杂）1原理
编辑以下以求a的b次方来介绍[1]
把b转换成
二进制数。
该二进制数第i位的权为
例如
11的二进制是1011
11 = 23×1 + 22×0 + 21×1 + 2o×1
因此，我们将a11转化为算
2实现
编辑快速幂可以用位
运算这个强大的
工具实现
1
band1{也就是取b的二进制最末位}
1
bshr1{就是去掉b的二进制最末位}
有了这个强大的工具，快速幂就好实现了！
以下为pascal的实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vara,b,n:int64;
functionf(a,b,n:int64):int64;
vart,y:int64;
begin
t:=1;
y:=a;
whileb<>0do
begin
if(band1)=1thent:=t*ymodn;
y:=y*ymodn;{这里用了一个很强大的技巧,y*y即求出了a^(2^(i-1))不知道这是什么的看原理}
b:=bshr1;{去掉已经处理过的一位}
end;
exit(t);
end;
begin
read(a,b,n);{n是模}
writeln(f(a,b,n));
end.
[1]
3代码比较
编辑常规求幂
1
2
3
4
5
6
7
int pow1(inta,intb)
{
int r=1;
while(b--)
r*=a;
return r;
}
二分求幂（一般）
1
2
3
4
5
6
7
8
9
10
11
12
int pow2(inta,intb)
{
int r=1,base=a;
while(b!=0)
{
if(b%2)
r*=base;
base*=base;
b/=2;
}
return r;
}
快速求幂（位操作）
1
2
3
4
5
6
7
8
9
10
11
12
intpow3(inta,intb)
{
intr=1,base=a;
while(b!=0)
{
if(b&1)
r*=base;
base*=base;
b>>=1;
}
returnr;
}
快速求幂（位运算，与pow3函数的实际行为相同，但看起来复杂）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
intpow4(intx,intn)
{
if(n==0)return1;
else
{
while((n&1)==0)
{
n>>=1;
x*=x;
}
}
intresult=x;
n>>=1;
while(n!=0)
{
x*=x;
if((n&1)!=0)
result*=x;
n>>=1;
}
returnresult;
}
本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请
点击举报。
