CSP-J/S 算法探秘——多种方式实现快速幂(上)
liebian365 2024-11-17 13:14 3 浏览 0 评论
算法探秘：多种方式实现快速幂（上）
幂运算是在设计算法过程中经常用到的基本运算，但是C++中没有对应的数学运算符表示，因此最基本的方式为：调用cmath库中的pow(x,y)，从而计算x的y次方的值。
使用pow(x,y)函数
pow函数能够计算x的y次幂，其中x为底数，y为指数。但需要注意的是，x、y和pow()函数的返回值都是浮点型，如果写成整型可能会出现下面的问题：
int a=3,b=3;
printf("%d的%d次方为%d\n",a,b,pow(a,b));
float x=3,y=3;
printf("%.1f的%.1f次方为%.2f",x,y,pow(a,b));由于在printf()中将pow()的格式控制符设置为%d，而pow()函数的返回值为float，因此输出会变为0。如果想要让计算结果为整型，需要用int()函数强制类型转换一下。
如果使用pow()函数来做洛谷平台的这一题：
最终评测结果为：
原因在于题目的数据规模：
由于数据规模过大，a的b次方结果肯定会超过long long类型的最大值，因此需要想别的办法来计算幂运算。
使用循环语句实现幂运算
如果pow()函数会溢出，那么可以回归到循环语句，a的b次方可以看做是b个a相乘，因此可以使用for循环来计算幂运算的值，同时要注意，由于最后的结果要对p取模，那么根据取模运算分配律：
(a * b) % p = ( (a % p) * (b % p) ) % p
每次循环做乘法的时候都进行取模，尽可能地避免答案溢出。参考代码如下：
long long a,b,p;
cin>>a>>b>>p;
long long ans=1;
for(long long i=0;i<b;i++){
ans=(ans%p)*(a%p)%p;
}
printf("%lld^%lld mod %lld=%lld",a,b,p,ans);最终评测结果为；
但还是出现了三个评测点TLE，即Time Limit Exceeded程序运行超时。再次看一下数据规模，发现指数b<2^31，2147483648，而时间限制为1s，1s内程序的操作次数最多为10^8次，显然不够用，因此还需要想办法来优化循环，减少次数。
使用递归算法进行快速幂
★★在数学中，幂运算遵循一些运算公式：
（1）同底数幂相乘，底数不变，指数相加
（2）不同底但同指数相乘，指数不变，底数相加
（3）幂的乘方公式，底数不变，指数相乘
在使用递归的快速幂算法中，我们就会用到幂运算的第一个性质，这个性质与分治算法的思想类似，可以将一个大指数的幂运算拆分成两个小指数的幂运算相乘，据此，我们可以写出递推公式：
结合公式，我们就可以写出对应的递归函数代码：
long long kpow(long long a,long long b)
{
if(b==1){ //递归边界
return a;
}
else{
long long ans1=kpow(a,b/2)%p;
//这里充分利用C++除法性质，b如果是奇数，b/2与(b-1)/2结果是一样的
ans1=(ans1*ans1)%p;
if(b%2==1)ans1=(ans1*a)%p;
return ans1%p;
}
}完整代码的评测结果如下：
通过递归算法，成功让幂运算的时间复杂度从O(b)降低到了O(logb)，从而能够在规定时间内AC了所有测试点。
总结
上述介绍的快速计算幂运算方式，都是使用了数学技巧来对幂运算进行的优化，但是如果能将快速幂与二进制相结合，就可以做到在O(1)的时间复杂度中计算出幂运算的结果，这个算法会在下期进行详细地介绍，敬请期待！！
相关推荐
- 快递查询教程，批量查询物流，一键管理快递
-
作为商家，每天需要查询许许多多的快递单号，面对不同的快递公司，有没有简单一点的物流查询方法呢？小编的回答当然是有的，下面随小编一起来试试这个新技巧。需要哪些工具？安装一个快递批量查询高手快递单号怎么快...
- 一键自动查询所有快递的物流信息 支持圆通、韵达等多家快递
-
对于各位商家来说拥有一个好的快递软件，能够有效的提高自己的工作效率，在管理快递单号的时候都需要对单号进行表格整理，那怎么样能够快速的查询所有单号信息，并自动生成表格呢？1、其实方法很简单，我们不需要一...
- 快递查询单号查询，怎么查物流到哪了
-
输入单号怎么查快递到哪里去了呢？今天小编给大家分享一个新的技巧，它支持多家快递，一次能查询多个单号物流，还可对查询到的物流进行分析、筛选以及导出，下面一起来试试。需要哪些工具?安装一个快递批量查询高手...
- 3分钟查询物流，教你一键批量查询全部物流信息
-
很多朋友在问，如何在短时间内把单号的物流信息查询出来，查询完成后筛选已签收件、筛选未签收件，今天小编就分享一款物流查询神器，感兴趣的朋友接着往下看。第一步，运行【快递批量查询高手】在主界面中点击【添...
- 快递单号查询，一次性查询全部物流信息
-
现在各种快递的查询方式，各有各的好，各有各的劣，总的来说，还是有比较方便的。今天小编就给大家分享一个新的技巧，支持多家快递，一次能查询多个单号的物流，还能对查询到的物流进行分析、筛选以及导出，下面一起...
- 快递查询工具，批量查询多个快递快递单号的物流状态、签收时间
-
最近有朋友在问，怎么快速查询单号的物流信息呢？除了官网，还有没有更简单的方法呢？小编的回答当然是有的，下面一起来看看。需要哪些工具？安装一个快递批量查询高手多个京东的快递单号怎么快速查询？进入快递批量...
- 快递查询软件，自动识别查询快递单号查询方法
-
当你拥有多个快递单号的时候，该如何快速查询物流信息？比如单号没有快递公司时，又该如何自动识别再去查询呢？不知道如何操作的宝贝们，下面随小编一起来试试。需要哪些工具？安装一个快递批量查询高手快递单号若干...
- 教你怎样查询快递查询单号并保存物流信息
-
商家发货，快递揽收后，一般会直接手动复制到官网上一个个查询物流，那么久而久之，就会觉得查询变得特别繁琐，今天小编给大家分享一个新的技巧，下面一起来试试。教程之前，我们来预览一下用快递批量查询高手...
- 简单几步骤查询所有快递物流信息
-
在高峰期订单量大的时候，可能需要一双手当十双手去查询快递物流，但是由于逐一去查询，效率极低，追踪困难。那么今天小编给大家分享一个新的技巧，一次能查询多个快递单号的物流，下面一起来学习一下，希望能给大家...
- 物流单号查询，如何查询快递信息，按最后更新时间搜索需要的单号
-
最近有很多朋友在问，如何通过快递单号查询物流信息，并按最后更新时间搜索出需要的单号呢？下面随小编一起来试试吧。需要哪些工具？安装一个快递批量查询高手快递单号若干怎么快速查询？运行【快递批量查询高手】...
- 连续保存新单号功能解析，导入单号查询并自动识别批量查快递信息
-
快递查询已经成为我们日常生活中不可或缺的一部分。然而，面对海量的快递单号，如何高效、准确地查询每一个快递的物流信息，成为了许多人头疼的问题。幸运的是，随着科技的进步，一款名为“快递批量查询高手”的软件...
- 快递查询教程，快递单号查询，筛选更新量为1的单号
-
最近有很多朋友在问，怎么快速查询快递单号的物流，并筛选出更新量为1的单号呢？今天小编给大家分享一个新方法，一起来试试吧。需要哪些工具？安装一个快递批量查询高手多个快递单号怎么快速查询？运行【快递批量查...
- 掌握批量查询快递动态的技巧，一键查找无信息记录的两种方法解析
-
在快节奏的商业环境中，高效的物流查询是确保业务顺畅运行的关键。作为快递查询达人，我深知时间的宝贵，因此，今天我将向大家介绍一款强大的工具——快递批量查询高手软件。这款软件能够帮助你批量查询快递动态，一...
- 从复杂到简单的单号查询，一键清除单号中的符号并批量查快递信息
-
在繁忙的商务与日常生活中，快递查询已成为不可或缺的一环。然而，面对海量的单号，逐一查询不仅耗时费力，还容易出错。现在，有了快递批量查询高手软件，一切变得简单明了。只需一键，即可搞定单号查询，一键处理单...
- 物流单号查询，在哪里查询快递
-
如果在快递单号多的情况，你还在一个个复制粘贴到官网上手动查询，是一件非常麻烦的事情。于是乎今天小编给大家分享一个新的技巧，下面一起来试试。需要哪些工具？安装一个快递批量查询高手快递单号怎么快速查询？...
欢迎 你 发表评论:
- 一周热门
- 最近发表
- 标签列表
-
- wireshark怎么抓包 (75)
- qt sleep (64)
- cs1.6指令代码大全 (55)
- factory-method (60)
- sqlite3_bind_blob (52)
- hibernate update (63)
- c++ base64 (70)
- nc 命令 (52)
- wm_close (51)
- epollin (51)
- sqlca.sqlcode (57)
- lua ipairs (60)
- tv_usec (64)
- 命令行进入文件夹 (53)
- postgresql array (57)
- statfs函数 (57)
- .project文件 (54)
- lua require (56)
- for_each (67)
- c#工厂模式 (57)
- wxsqlite3 (66)
- dmesg -c (58)
- fopen参数 (53)
- tar -zxvf -c (55)
- 速递查询 (52)