首页 > 代码库 > 快速幂求解

快速幂求解

顾名思义,快速幂就是快速算底数的n次幂。其时间复杂度为 O(log?N), 与朴素的O(N)相比效

用法:用于求解 a 的 b 次方,而b是一个非常大的数,用O(n)的复杂度会超时。那么就需要这个算法,注意它不但可以对数求次幂,而且可用于矩阵快速幂。

把b转换成二进制数,该二进制位数有logb位;该二进制数第i位的权为2i-1
 
例如:
技术分享     11的二进制是1011
11 = 23×1 + 22×0 + 21×1 + 2o×1
因此,我们将a11转化为算技术分享
 
 

快速幂求解