快速幂

---

快速幂用于快速计算指数（$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;
}