快速幂C++实现
2024-08-27 00:24:04
很明显,这个题目不能用简单的\(for\)循环+\(mod\)来完成,因为指数\(p\)已经达到了长整型,直接循环来完成的话肯定会超时的。
那么快速幂就应运而生了.
什么是快速幂呢?
利用二进制扩大底数,减少计算次数,经常会涉及到到类似\(a^b\mod p\)的运算,这里的\(b\)常常会很大,导致我们不能\(for\)循环计算。
那么怎么用代码实现呢?
首先,为了保险我们把所有的数据类型都设置为long long
。
然后为了方便,把快速幂写作一个函数,参数就是上面提到的\(a,b,p\),这是个好习惯
快速幂顾名思义,就是快速算某个数的多少次幂。其时间复杂度为 O(logN),与朴素的O(N)相比效率有了极大的提高。
简单来说,就是个二分求模的过程。
至于二分过程,无非就是扩大底数减少指数,达到降低时间复杂度的效果。
但要注意的是,因为快速幂普遍会有一个取模操作,所以在过程中就要进行\(mod\)哦。
代码也很简单,就以自定义函数的方式贴下面吧...
long long qpow(long long a,long long b,long long p)
{
long long x=a;
long long ans=1;
while(b)
{
if(b%2!=0)
ans*=x;
ans%=p;
x*=x;
x%=p;
b/=2;
}
return ans;
}
ov.
最新文章
- css3盒模型
- dedecms 相关文章likearticle
- Centos压缩与打包
- sublimetext ruby 插件
- FIM相关报错汇总
- Android动态Java代码调整window大小
- GitHub简单使用入门
- 【CentOS】Eclipse插件egit使用
- java正则表达式Pattern和Matcher
- OC基础6:多态、动态类型和动态绑定
- 插件化-开启另外应用的activity
- 在Vista以上版本运行WTL程序,有时候会提示“这个程序可能安装补正确...”的错误
- Java基础07 包
- 【Machine Learning in Action --5】逻辑回归(LogisticRegression)从疝气病预测病马的死亡率
- Quartz_理解2
- 深入理解立即执行函数(function(){})();
- git 快速入门
- Python内置函数(52)——getattr
- iptables 添加raw提高服务器性能之路
- Shell编程(六)awk工具