快速幂专题

摘要：
深入快速幂。

朴素快速幂

快速幂，二进制取幂（Binary Exponentiation，也称平方法），是一个在 $O(logn)$ 的时间内计算 $a^n$ 的小技巧，而暴力的计算需要 $O(n)$ 的时间。

二进制取幂 的想法是，我们将取幂的任务按照指数的 二进制表示 来分割成更小的任务。

举例：计算 $3^{13}$.

将$3^{13}$拆成：
$3^{13} = 3^{(1101)_2} = 3^8 \cdot 3^4 \cdot 3^1$

我们可以预处理出来$3^1, 3^4, 3^8$，一共只需计算3次得到答案。
3是怎么来的呢？
因为$3^{2^3} < 3^{13} < 3^{2^4}$，所以$3 = \lfloor \log_2(13) \rfloor$。

那么，对于$a^n$，因为$n$有$\lfloor \log_2(n) \rfloor + 1$个二进制位，那么当我们预处理出:
$a^1, a^2, a^4, a^8,…,a^{2^{\log_2(n)}}$ 后，就只需计算$O(logn)$次乘法即可计算出$a^n$。

而这个预处理的每一个项，都可以由前面的项计算得到。
从二进制最低位到最高位，假设全为1，那么每一项都等于前一项的平方；
假设从低到高位依次为$101$，那么第一项显然为底数本身，第二项为$1$，第三项并非由第二项得出，而是第一项的平方的平方。

根据这个思想，写代码的时候，我们动态地让指数右移，让$a$与最低位$1$相乘，然而每右移一次，相当于指数$b$除2，等价于$a$对应地更新成$a^2$。当最低位不为$1$时，则$a$继续更新，且不与最低位相乘。

迭代

long long fastpow(long long a, long long n)
{
    long long res = 1;
    for (; n; n >>= 1) {
        if (n & 1) res *= a;
        a = a * a;
    }
    return res;
}

递归

待更新。