快速幂，二进制取幂（Binary Exponentiation，也称平方法），是一个在 $O(log n)$的时间内计算 $a^n$ 的小技巧，而暴力的计算需要$O(n)$的时间。而这个技巧也常常用在非计算的场景，因为它可以应用在任何具有结合律的运算中。其中显然的是它可以应用于模意义下取幂、矩阵幂等运算，我们接下来会讨论。
xianhai
,
2022-03-19 16:52:07
,
所有人可见
,
阅读 311
快速幂，二进制取幂（Binary Exponentiation，也称平方法），是一个在 $O(log n)$的时间内计算 $a^n$ 的小技巧，而暴力的计算需要$O(n)$的时间。而这个技巧也常常用在非计算的场景，因为它可以应用在任何具有结合律的运算中。其中显然的是它可以应用于模意义下取幂、矩阵幂等运算，我们接下来会讨论。
