OI Wiki 快速幂
快速幂 快速幂 目录
模意义下取幂
计算斐波那契数
多次置换
加速几何中对点集的操作
定长路径计数
模意义下大整数乘法
快速乘
高精度快速幂
同一底数与同一模数的预处理快速幂
参考资料与注释
快速幂,二进制取幂(Binary Exponentiation,也称平方法),是一个在 的时间内计算 的小技巧,而暴力的计算需要 的时间.
这个技巧也常常用在非计算的场景,因为它可以应用在任何具有结合律的运算中.其中显然的是它可以应用于模意义下取幂,矩阵幂等运算,我们接下来会讨论.
计算 的 次方表示将 个 乘在一起:个.然而当 太大的时侯,这种方法就不太适用了.不过我们知道:.二进制取幂的想法是,我们将