【知识点】
顾名思义，快速幂就是快速算底数的 $n$ 次幂。其时间复杂度为 $O(log₂N)$， 与朴素的 $O(N)$ 相比效率有了极大的提高。快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。
让我们先来看一个简单的例子：
$3^{10}=3*3*3*3*3*3*3*3*3*3$ 尽量想办法把指数变小来，这里的指数为 $10$。
$3^{10}=(3*3)*(3*3)*(3*3)*(3*3)*(3*3) \leftrightarrow$
$3^{10}=(3*3)^5 \leftrightarrow$
$3^{10}=9^5$
此时指数由 $10$ 缩减一半变成了 $5$，而底数变成了原来的平方，求 $3^{10}$ 原本需要执行 $10$ 次循环操作，求 $9^5$ 却只需要执行 $5$ 次循环操作，但是 $3^{10}$ 却等于 $9^5$。我们用一次（底数做平方操作）的操作减少了原本一半的循环量，特别是在幂特别大的时候效果非常好。
我们知道：$a^{b+c}=a^b \cdot a^c,\ a^{2b}=a^b \cdot a^b=(a^b)^2$。二进制取幂的想法是，我们将取幂的任务按照指数的 二进制表示 来分割成更小的任务。
首先我们将 $n$ 表示为 $2$ 进制，举一个例子：
$3^{13}=3^{(1101)_2}=3^8 \cdot 3^4 \cdot 3^1$
因为 $n$ 有 $\lfloor log_2n \rfloor+1$ 个二进制位，因此当我们知道了 $a^1,\ a^2,\ a^4,\ a^8, \cdots,\ a^{2^{\lfloor log_2n \rfloor}}$ 后，我们只用计算 $\Theta (\text{log}n)$  次乘法就可以计算出 $a^n$。举一个例子：
$3^1=3$
$3^2=(3^1)^2=3^2=9$
$3^4=(3^2)^2=9^2=81$
$3^8=(3^4)^2=81^2=6561$
因此为了计算 $3^{13}$，我们只需要将对应二进制位为 $1$ 的整系数幂乘起来就行了：
$3^{13}=6561 \cdot 81 \cdot 9 \cdot 1=1594323$
将上述过程说得形式化一些，如果把 $n$ 写作二进制为 $(n_{t}n_{t-1} \dot n_{1}n_{0})_2$，那么有
$n=n_{t}2^{t}+n_{t-1}2^{t-1}+n_{t-2}2^{t-2}+\cdots+n_{2}2^{2}+n_{1}2^{1}+n_{0}2^{0}$
其中 $n_i \in \{0,\ 1\}$。那么就有
$a^n=a^{n_{t}2^{t}+n_{t-1}2^{t-1}+n_{t-2}2^{t-2}+\cdots+n_{2}2^{2}+n_{1}2^{1}+n_{0}2^{0}}=a^{n_{0}2^{0}} \times a^{n_{1}2^{1}} \times \cdots \times a^{n_{t}2^{t}}$
根据上式我们发现，原问题被我们转化成了形式相同的子问题的乘积，并且我们可以在常数时间内从 $2^i$ 项推出 $2^{i+1}$ 项。

【代码实现】
【递归版本】

LL binpow(LL a, LL b) { 
    if (b==0) {return 1;} 
    LL res=binpow(a, b/2); 
    if (b%2) {return res*res*a;} 
    else {return res*res;}
}

【非递归版本】

LL binpow(LL a, LL b) { 
    LL res=1; 
    while (b>0) { 
        if (b&1) {res=res*a;} 
        a=a*a; 
        b>>=1; 
    } 
    return res; 
}

尽管两者的理论复杂度是相同的，但第二种在实践过程中的速度是比第一种更快的，因为递归会花费一定的开销。
在实际计算中，由于快速幂计算的结果都很大，一般题目都会对结果进行取模运算。