梁山武功排名,品色堂免费图片,酷毙电影网
\[ 快速幂算法,可以加快运算速度,使用快速幂算法时间复杂度为o(logn) \]
\[ 以2^{50}为例 \]
在不使用数学函数的情况下,使用遍历的方法,时间复杂度是o(n),需要遍历50次对吧。
但是如果使用快速幂的话,那就快多了。具体是如何运算,先将50转化成2进制数 110010,那么50就可以转化为
\[
2^5+2^4+2^1
\]
这是如何实现的呢?我们使用二进制很轻松就可以做到这样了。
\[
110010 = 1*2^5 + 1*2^4 + 0*2^3 + 0*2^2 + 1*2^1 + 0*2^0
\]
\[ 2^{50} = 2^{2^5} * 2^{2^4} *2^{2^1} \]
很显然这样运算的话比遍历快的多得多了。
非常简洁b&1的意思是判断二进制最后一位为不为1,也可以使用 b%2代替;b>>1的意思是二进制右移一位(通俗的讲就是去掉二进制最后一位),也可使用b/2代替。关于位运算,以后再补充。
long long ksm(long long a, long long b) { long long ans; while(b) { if(b&1) ans *= a; a *= a; b = b>>1; } return ans; }
这就是快速幂的一个模板了,很简单,易记。
来吧,来搞12.2的c题吧。
stat | origin | title | problem title |
---|---|---|---|
solved | c | hdu 1097 | a hard puzzle |
题中给的数据范围很大,如果直接暴力的话,那肯定就爆炸了,long long也装不下,所以此时非常适合使用快速幂配合运算过程中的同余取模,这样既取了最后一位,还减小了数,运算速度也极快。
#include<stdio.h> typedef long long ll; //long long使用的 ll ksm(ll a, ll b) //太多,简化为ll { ll ans = 1; while(b) { if( b&1) ans = (ans*a)%10; //对每次运算都模10 a = a*a%10; //取最后一位 b = b >> 1; } return ans; } int main() { ll a, b; while(~scanf("%lld%lld", &a, &b)) { printf("%lld\n", ksm(a,b)); } return 0; }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论