# 快速幂

***

快速幂用于快速计算指数（$$2^n$$），主要思想是二分。

由于计算机计算单个乘法比多个乘法快得多，所以利用二分的思想来减少乘法运算次数可以提高速度。

例：$$7^{10} = 7*7*7\*...*7$$ 需要计算9次乘法，而先计算$$7^5$$再计算$$7^{10}$$，就只用计算$$7^5 = 7*7*7*7*7$$和$$7^{10}=7^5*7^5$$，只用5次乘法。

以此类推，得到一个递归二分的策略：

$$
n是奇数：a^n = a^{n-1}\*a^n\ n是偶数：a^n = a^{n/2}\*a^{n/2}\ n=0：a^n = 1
$$

写成代码：

```
typedef long long ll;
ll qpow(ll a, ll n)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 1)
        return qpow(a, n - 1) * a;
    else
    {
        ll temp = qpow(a, n / 2);
        return temp * temp;
    }
}
```

这是递归版本的快速幂。 可以看到，这里二分的操作可以和二进制的右移对应，于是可以用二进制的方式理解：

$$7^{10} =7^{\[1010]\_2}$$ ，于是$$7^{10}=7^{\[1000]\_2} \* 7^{\[0010]\_2}$$

由于上面的递归形式递归会耗费时间，所以用二进制的思路将上面的递归改成循环形式会更好。

具体方法：由于每个二进制位表示一次平方，所以我们对n的每个二进制位，让底数进行一次自乘，如果对应的二进制位为1，则将此时的底数乘给ans，达到例如 $$7^{\[1010]\_2}=7^{\[1000]\_2} \* 7^{\[0010]\_2}$$的效果。

代码：

```
int qpow(int a, int n){
    int ans = 1;
    while(n){
        if(n&1)        //如果n的当前末位为1
            ans *= a;  //ans乘上当前的a
        a *= a;        //a自乘
        n >>= 1;       //n往右移一位
    }
    return ans;
}
```