快速幂优美算法

张开发
• 2026/4/16 16:28:39 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

快速幂优美算法
来咱彻底扔掉公式、扔掉难懂术语用掰手指头数数的方式讲到你秒懂LL qpow(LL a,LL b,int mod) { LL tmpa; LL ans1; while(b){ if(b1) ans(ans*tmp)%mod; b1; tmptmp*tmp%mod; } return ans; }先定一个超简单目标算是什么本来是2×2×2×2×2但我们换个偷懒拆法514所以*只需要乘2 个大数不用乘 5 次现在看5 的二进制是 101从右边往左边看这三个数字1 0 1对应最右边第一个数1 → 对应中间第二个数0 → 对应最左边第三个数1 → 对应规则超简单✅ 数字是1这个数要留下来相乘❌ 数字是0这个数直接扔掉不乘回到代码里的 b 1b 1作用只看当前最右边那一个数字是啥第一轮b5二进制 101最右边是1 按照规则要乘把当前底数塞进答案里第二轮b 往右挪一位变成 10最右边是0 按照规则不要啥也不乘跳过第三轮b 再往右挪一位变成 1最右边是1 按照规则要乘再塞一次再看 tmp底数在干嘛tmp 一直在变大2 → 4 → 16刚好就是我们要的,,每看一位二进制就对应一个 tmp位是 1 → 乘这个 tmp位是 0 → 丢这个 tmp终极大白话总结b 1就是在问一句话现在最右边这个二进制小格子里写的是 1 还是 0写 1这一份数字我要乘进去写 0这一份数字我不要直接扔就这么简单没有任何高深数学

更多文章