主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
快速幂
最后更新于 2025-08-27 19:39:00
作者
wxhd5
分类
算法·理论
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
这篇文章将以通俗易懂的方式教会你快速幂的原理！！！ 那么，话不多说，$\texttt{let's go}!$ --- ## 一.普通幂运算的弊端 我们之前的幂运算，都是循环累乘的，对于$n^k$的计算，时间复杂度为$O(k)$，当$k>1e8$时，就十分危险了，容易$\texttt{\blue{TLE}}$ ## 二.快速幂的原理 举个栗子，现在我们要计算$n$的$6$次幂，那么我们可以这样做： **step1：** 将$6$转为二进制 $$n^6 = n^{110(2)}$$ **step2：** 将$6$的二进制保留权重累加的形式转回十进制 $$n^{110(2)} = n^{0*2^0+1*2^1+1*2^2}$$ **step3：** 根据公式$a^n*a^m = a^{n+m}$展开 $$n^{0*2^0+1*2^1+1*2^2} = n^{0*2^0}*n^{1*2^1}*n^{1*2^2}$$ **step4：** 循环计算即可 这样，对于计算$n^k$的时间复杂度就成功下降到了$k的二进制位数$，也就是$O(logk)$
正在渲染内容...
点赞
0
收藏
0
