快速幂取模及其应用

• 爱心 发布于
• 1649 收藏

快速幂取模 用法：用于求解 a 的 b 次方，而b是一个非常大的数，用O（n）的复杂度会超时。那么就需要这个算法，注意它不但可以对数求次幂，而且可用于矩阵快速幂。 假如求 x ^ n 次方 我们可以把 n 表示为 2^k1 + 2k2  + 2^k3....，可以证明所有数都可以用前式来表示。（其实就是二进制表示数的原理） 那么 x^n = x^2^k1 * x^2^k2 * x^2^k3...