
AcWing 89 a^b
发布日期:2021-05-28 16:29:42
浏览次数:22
分类:精选文章
本文共 615 字,大约阅读时间需要 2 分钟。
这道题目是关于快速幂算法的实现,主要需要注意的是测试用例中当模数p为1时的情况。在这种情况下,任何数对1取模都会得到0,因此在快速幂函数中,初始值ans应设为0 % p。
以下是实现代码:
#includeusing namespace std;typedef long long ll;ll binaryPow(ll a, ll b, ll p) { ll ans = 1 % p; // 初始化为1 % p while (b > 0) { if (b & 1) { ans = (ans * a) % p; // 如果b的最低位是1,则ans乘以a并对p取模 } a = (a * a) % p; // a平方后对p取模 b >>= 1; // b右移1位,相当于整除以2 } return ans;}int main() { int a, b, p; cin >> a >> b >> p; cout << binaryPow(a, b, p) << endl;}
需要注意的是,在实现快速幂算法时,这里的初始值需要特别处理。如果模数p为1,那么无论a和b的值是什么,最终结果都应该是0。因此在初始化时,应将ans设为1 % p,这样当p=1时,会自动变为0,符合预期结果。
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2025年04月17日 10时22分40秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Android 架构组件 – 让天下没有难做的 App
2019-03-13
启动MongoDB出现1053错误
2019-03-13
网络对抗技术-Exp2-后门原理与实践 20181314
2019-03-13
能解决数据可视化大屏需求的3款可视化工具
2019-03-13
欢迎来到小迪博客
2019-03-13
【Altium Designer21】工作栏中文解析
2019-03-13
[87]用secureCRT连接虚拟机中的Ubuntu系统,出现“远程主机拒绝连接”错误
2019-03-13
Shell脚本防DNS攻击检测并删除肉机IP
2019-03-13
如何在VSCode中定制JSON的IntelliSense
2019-03-13
椭圆曲线的定义
2019-03-13
多代理区块链框架客户端的操作
2019-03-13
RSA操作中的公钥和私钥的生成
2019-03-13
go语言中类的继承和方法的使用
2019-03-13
caffe训练的时候遇到的text-format 错误解决方案。
2019-03-13
Java 8新特性(一):Lambda表达式
2019-03-13
Little Zu Chongzhi's Triangles
2019-03-13
算法入门
2019-03-13
cf-A. Wet Shark and Odd and Even(水)
2019-03-13
Train Problem II(卡特兰数+大数乘除)
2019-03-13
一些技术博客
2019-03-13