本文主要讲解平方求幂（快速幂）相关，凡涉及大整数，都会进行对定值取模等处理，所以存储越界导致的错误、位数过多导致的单次运算缓慢的问题，不在考虑范围之内。
“幂”在许多地方常被用到，如Hash 相关、费马小定理、进制转换等。
一般来说，我们要求a的n次方 ，只需要将 a乘 n 次即可，时间复杂度为
。
但有时， n极大，这种方法需要的时间开销是不可接受的。
比如，求 
如果我们直接计算多个这样的式子，至少在目前主流计算机中，所用时间以分钟计。
我们考虑如何优化对 a的n次方 的计算。
这样我们就可以写出一份递归的伪代码：
function power(a, n): if n = 0 then return 1 t := power(a, (n - n mod 2) / 2) if n mod 2 = 1 then: return t^2 * a else: return t^2
每次将数据规模缩小为原来的一半，这种方法的时空复杂度是 
。
function power(a, n): pow[0...log n], pow[0] := 1 for i: 1 to inf if (2^i > n) break else pow[i] = pow[i - 1]^2 res := 1 for i: 1 to inf if (2^i > n) break else: if (n bitand 2^i) res = res * pow[i] return res # n bitand 2^i 可理解为 n 在二进制表示下含 2^i 位 function power(a, n): res := 1, p := a while n > 0: if (n bitand 1) then res = res * a p = p^2, n = n >> 1 return res # bitand 表示按二进制位与，>> 表示按二进制位右移（可理解为除以 2 下取整）。
function times(a, b, m): if b = 0 then return 0 t := times(a, (b - b mod 2) / 2, m) if b mod 2 = 1 then: return ((t + t) mod m + a mod m) mod m else: return (t + t) mod m
同样地，也可以对 进行二进制拆分。
function power(a, b, m): res := 0 while b > 0: if (b bitand 1) then res = (res + a) mod m a = (a + a) mod m, b = b >> 1 return res # bitand 表示按二进制位与，>> 表示按二进制位右移（可理解为除以 2 下取整）。
这样，我们用 
的时间复杂度算出了大数乘积取模的值。俗称“龟速乘”。
事实上，平方求幂的思想，在任何具有结合律的、参与运算的数据相同的运算中，都可以使用。
如矩阵乘法等。
好了，快速求幂的方法就讲到这里，如果对你有哦帮助，欢迎点赞哦~~
