快速幂/乘算法

快速幂算法

通常情况下,如果要求一个数的平方,例如$a^{n}$,我们通常会想到n个a相乘来得到结果,它的复杂度为O(n),为线性的复杂度,这种算法效率较低,那么我们有没有其他的算法呢?答案是肯定有的。接下来就介绍快速幂算法。
我们都学习过二进制与十进制的转换,知道一个进制数的值可以表示为各个数位的值与权值之积的总和,假设我们要求$a^{11}$,可以将$a^{11}$中的11转换为$2^{k}=11$,再把11转换为二进制,也就是1011。二进制从最右边开始为第0位,向左依次为第1、第2位…如果一个二进制序列有m位,那么每个位对应的数值就是$2^{m-1}$,权值就是0或1。
接下来,我们回到11的二进制1011,将他转换为10进制,那就是$2^{0}×1+2^{1}×1+2^{2}×0+2^{3}×1$=1+2+0+8=11
所以$a^{11}$就可以转换为$a^{1+2+0+8}$=$a×a^{2}×a^{0}×a^{8}$,这样就可通过位操作符快速计算乘方,其复杂度为O(logn)
代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
long long ksm(long long a,long long b)
{
int ans = 1,base = a;
while(b != 0){
if(b & 1 != 0){
ans *= base;
}
base *= base;
b >>= 1;
}
return ans;
}

其中b & 1 != 0用来判断当前权值是否为非0,非0说明权值为1,则继续执行代码。
ans *= base用来实现1×$a^{1}×a^{2}×a^{4}×a^{8}…$
base *=base可以实现$a^{1}、a^{2}、a^{4}、a^{8}…$
b >>=1二进制序列向右移动一位,删除最低一位。
while(b != 0) 当b的二进制序列都不为0时,执行代码。

  • © 2015-2019 VicenteSWL
  • Hexo Theme Ayer by shenyu
    • PV:
    • UV: