快速幂
快速幂，二进制取幂（Binary Exponentiation，也称平方法），是一个在$\Theta(\log n)$ 的时间内计算$a^n$的小技巧，而暴力的计算需要$\Theta(\log n)$的时间。而这个技巧也常常用在非计算的场景，因为它可以应用在任何具有结合律的运算中。其中显然的是它可以应用于模意义下取幂、矩阵幂等运算，我们接下来会讨论。
算法描述
计算$a$的$n$次方表示将$n$个$a$乘在一起：$a^{n} = \underbrace{a \times a \cdots \times a}_{n\text{ 个 a}}$ 。然而当$a,n$太大的时侯，这种方法就不太适用了。不过我们知道：$^{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_2 n \rfloor + 1$ 个二进制位，因此当我们知道了$a^1, a^2, a^4, a^8, \dots, a^{2^{\lfloor \log_2 n \rfloor}}$
