快速幂

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

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

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

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

$$
n是奇数：a^{n = a}*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;
}