首页 > 代码库 > 快速幂求解
快速幂求解
顾名思义,快速幂就是快速算底数的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转化为算
快速幂求解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。