快速幂

快速幂就是怎么样快速求一个数的幂，一般而言，求幂直接就是连乘，比如a⁵，ans就是a*a*a*a*a,这样做时间复杂度是O(n)。

而使用快速幂算法可以使时间复杂度降低到O(logn)，它是以是数的二进制作为基础，利用二进制的特性进行计算。

举个例子：11的二进制是1011，于是11=2³×1+2²×01+2¹×1+2⁰×1，那么a¹¹=a^{2³×1+2²×0+2¹×1+2⁰×1}=a^2³+2¹+2⁰=a⁸⁺²⁺¹=a⁸*a²*a¹。

用b表示指数，a表示上面的a，每一步计算时，先判断b的奇偶性，如果是偶数，那么答案ans就乘上a的当前值，每次当b不等于0

进行循环时，a=a*a；随时准备乘上ans，这样a就呈现a¹->a²->a⁴->a⁸的变化。模拟一下a¹¹的算法：

1.当前b不等于0，（11&1！=0）于是ans*=a(此时ans=a)，a=a*a=a²，b除以2，即二进制右移一位，得到二进制b=101。

2.当前b不等于0，（101&1！=0）于是ans*=a²(此时ans=a³)，a=a²*a²=a⁴，b除以2，得到二进制b=10。

3.当前b不等于0，（10&1==0）于是不执行ans*=a⁴(此时ans=a³)，a=a⁴*a⁴=a⁸，b除以2，得到二进制b=1。

4.当前b不等于0，（1&1！=0）于是ans*=a⁸(此时ans=a¹¹)，a=a⁸*a⁸=a¹⁶，b除以2，得到二进制b=0。

5.当前b等于0，结束。

其他次幂思路相同。

代码如下：

 1 int FastPower(int a,int b)
 2 {
 3     int ans=1;//一定注意赋初值为1
 4     while(b!=0)
 5     {
 6         if(b&1)//其实就是b&1！=0时执行，相当于(b%2!=0)，即b为奇数时
 7         {
 8             ans=ans*a;
 9         }
10         a=a*a;
11         b>>=1;//b的二进制右移一位，即b除以2
12     } 
13     return ans;
14 }

入门题目可以看看这个：hdu2035 人见人爱A^B 题解：hdu2035 人见人爱A^B题解

典型题目：

快速幂取模（取余），以51nod1046 A^B mod C为例，

在相应的位置%一个数即可，详见题解：51nod1046 A^BmodC题解

快速幂解法还有另外一个思路，就是递归地解决：

假如说有两个数a和b，让你求a的b次方，那么

比如3¹¹，可以这样递归地想：

3¹¹=3 * 3¹⁰

3¹⁰=3⁵* 3⁵

3⁵=3 * 3⁴

3⁴=3² * 3²

3²=3¹ *3¹

3¹=3¹* 3⁰

到头了。。

观察一下，可以分为两种情况：

第一，当b（即指数）为偶数时，a^b=a^b/2 * a^b/2;

第二，当b（即指数）为奇数时，a^b=a * a^b/2;

递归代码如下：（有点类似二分）

 1 int FastPow(int a,int b)
 2 {
 3     if(b==0)
 4     {
 5         return 1;
 6     }
 7     else if(b&1)//相当于(b%2==1) 
 8     {
 9         return a*FastPow(a,b/2);
10         //return a*FastPow(a,b/2)%c;(如果题目要求求余) 
11     }
12     else
13     {
14         int tmp=FastPow(a,b/2);
15         return tmp*tmp;
16         //return tmp*tmp%c;(如果题目要求求余)
17     }
18 }

题目要求求余的话多传入一个模数c即可，必要时开long long