网站设计开发软件有哪些,免费源码资源源码站,网站开发与设计模板,seo属于技术还是营销文章目录 1. 什么是快速幂2. 暴力求解代码实现缺陷分析 3. 优化一#xff1a;取模运算的性质4. 优化二#xff1a;快速幂算法的核心思想5. 终极优化#xff1a;位运算优化6. 源码 这篇文章我们来一起学习一个算法——快速幂算法。 1. 什么是快速幂 顾名思义#xff0c;快速… 文章目录 1. 什么是快速幂2. 暴力求解代码实现缺陷分析 3. 优化一取模运算的性质4. 优化二快速幂算法的核心思想5. 终极优化位运算优化6. 源码 这篇文章我们来一起学习一个算法——快速幂算法。 1. 什么是快速幂 顾名思义快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N) 与朴素的O(N)相比效率有了极大的提高。 那快速幂算法呢一般就是用来解决如下的问题 我们看到它的取值范围是比较大的所以我们可以用long long 2. 暴力求解
代码实现
那这个问题呢乍一看很简单 我们可以考虑用循环或者使用pow函数直接计算a^b的值然后对c去模即可。 缺陷分析
但是呢这样写我们的算法其实是有去缺陷的 首先它的时间复杂度是O(b)而上面题目中b的取值是【010^18】。 所以当b的取值比较大的时候时间复杂度就会很大那么算法的效率就比较低。 此外这里的ret不断乘等以a它的范围是很有可能超过long long 的。 那一旦溢出的话结果可能就错了。 所以我们要想办法对该算法进行优化
3. 优化一取模运算的性质
首先我们可以根据取模运算的性质进行第一重优化 取模运算是满足这样一条性质的 (a*b)%c((a%c)*(b%c))%c 大家有兴趣可以自己证明一下 那这样的话我们之前是每次让ret*a乘等b次最后再去模。 那现在我们可以在每次ret*a之后都对ret进行一次取模 那这样的话ret就不太容易溢出了。 long long fastPow(long long a, long long b, long long c)
{long long ret 1;for (int i 0; i b; i){ret * a;ret % c;}return ret % c;
}但是是否仍然有缺陷呢 它的时间复杂度并没有得到优化还是O(b) 所以我们再来想办法优化
4. 优化二快速幂算法的核心思想 快速幂算法的核心思想就是每一步都把指数分成两半而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小所需要执行的循环次数也变小而最后表示的结果却一直不会变。 我们来举个例子 比如算3^10 那其实可以这样写 3^10(3^2)^59^59*9^49*81^2 那观察这个式子其实我们能发现这样的规律 如果指数是是偶数的话那么指数除以2底数平方前后的值是相等的。ret*3^10ret*(3^2)^5如果指数是奇数的话先将ret*底数然后依然是指数除以2底数平方前后值相同ret*9^5ret*9*81^2 那我们来算一下这种写法的时间复杂度 这样优化之后呢每次指数的值都会/2即b/2那之前我们要循环b次现在就是O(logb)即以2为底b的对数。 那我们来写一下代码 那此外为了防止输入的a过大的话我们上来可以直接对a取模 5. 终极优化位运算优化
那针对上面的代码有两处地方我们其实还可以进行一个优化 首先 判断指数是偶数还是奇数这里还有一种更高效的方法就是使用位运算让b1因为1的补码只有最后一位为1其余全为0如果b是奇数的话那它的最后一位为1b1的结果就是1如果b是偶数那最后一位为0b1的结果是0 然后就是 b/2这里我们可以用b1代替整数算术右移一位相当于除以2并向下取整 关于移位操作符如果大家遗忘了可以看 【C操作符详解】之 移位操作符 我找了一道OJ我们可以来测试一下 没有问题
6. 源码
#include iostream
using namespace std;
long long fastPow(long long a, long long b, long long c)
{long long ret 1;a % c;while (b){if (b 1){ret * a;ret % c;}a * a;a % c;b 1;}return ret;
}int main()
{long long a 0;long long b 0;long long m 0;cin a b m;cout fastPow(a, b, m) endl;return 0;
}
