首页 > 其他 > 详细

来嘛~整理一下快速幂

时间:2020-09-16 21:18:41      阅读:16      评论:0      收藏:0      [点我收藏+]

标签:快速幂算法   我们   最简   res   base   快速   

我才发现我虽然学了这么长时间的OI,我居然连快速幂是什么都不知道。

以至于当自己卡在“完美数”那道题,而后去看题解的时候。

#####我发现了一个我虽然听过无数次但是从来不会写的算法。

##快速幂

于是我飞快地baidu了一下。

找到了一篇炒鸡棒哒博客。

不得不说那篇博客写的非常的浅显易懂。

于是乎,

我只用了不到10分钟就完全搞懂了快速幂。

正好嘛~过来写个博客扩充一下自己的博客。


首先先描述一下这个快速幂算法的思路:

我们都知道,如果想要求一个幂,

我们最普通的代码需要的是循环指数次乘积操作。

而快速幂算法能够大大优化时间的复杂度。

我们可以将所要求的指数减半,分成两个底数的平方的指数的一般次幂。

但是,看到这里显然有的人就会提出疑问:

如果我的指数是奇数怎么解决呢?

显然-1即可。

long long fastPower(long long base,long long power){
	lont lont result=1;
	while(power>0){
		if(power&1){
			result=result*base%1000;
		}
		power>>=1;
		base=(base*base)%1000;
	}
	return result;
}

copy的代码如上面,

但是那个并不是正经的快速幂函数,

只是一道十分普通的题的最简便写法。

仅此而已。

所以真正的快速幂还是要自己写的。

嗯,就这样。

我似乎非常成功的水了一篇博客。

rua

——by 某个不知名的精分患者

来嘛~整理一下快速幂

标签:快速幂算法   我们   最简   res   base   快速   

原文:https://www.cnblogs.com/JingFenHuanZhe/p/KuaiSuMi0916.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号