快速幂算法简析

当然是快速幂啦

快速幂的目的就是做到快速求幂,假设我们要求a^b,按照朴素算法就是把a连乘b次,这样一来时间复杂度是O(b)也即是O(n)级别,快速幂能做到O(logn),快了好多好多。它的原理如下:

  假设我们要求a^b,那么其实b是可以拆成二进制的,该二进制数第i位的权为2^(i-1),例如当b==11时

1
a^11=a^(2^0+2^1+2^3)

11的二进制是1011

1
11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1

因此,我们将a¹¹转化为

1
a^11 = a^(2^0)* a^(2^1)* a^(2^3)

看出来快的多了,原来算11次,现在算三次,但是这三项貌似不好求的样子….不急,下面会有详细解释。

由于是二进制,很自然地想到用位运算这个强大的工具: & 和 >> ,&运算通常用于二进制取位操作,例如一个数 & 1 的结果就是取二进制的最末位。还可以判断奇偶:x&1== 0为偶,x&1==1为奇。>>运算比较单纯,就是二进制去掉最后一位。
  

1
2
3
4
5
6
7
8
9
10
11
12
13
  int KsmPow(long long a,long long  b)
  {
int ans=1;
while(b)
{
if(b&1)
  ans*=a;

a*=a;
b>>=1;
}
return ans;
}

代码很短,死记也可行,但最好还是理解一下吧,其实也很好理解,以b=11为例,b=>1011,二进制从右向左算,但乘出来的顺序是 a^(2^0)*a^(2^1)*a^(2^3),是从左向右的。我们不断的让a*=a目的即是累乘,以便随时对ans做出贡献。

其中要理解a*=a这一步:因为 a*a=a^2,下一步再乘,就是a^2*a^2=a^4,然后同理 a^4*a^4=a^8,由此可以做到a-->a^2-->a^4-->a^8-->a^16-->a^32指数正是 2^i ,再看上面的例子,a¹¹= a1*a2*a8,这三项就可以完美解决了,快速幂就是这样。

指数函数是爆炸增长的函数,所以很有可能会爆掉int的范围,根据题意选择 long long或者mod某个数。