您当前位置：首页 > php开源 > php教程 > hdu2035 人见人爱A^B（快速幂取模）

hdu2035 人见人爱A^B（快速幂取模）

来源：程序员人生发布时间：2015-08-04 07:48:07 阅读次数：3432次

题目链接：hdu 2035 人见人爱A^B

很早的时候做的1道题了，今天想一想把他翻了出来，写篇文章来为不知道快速幂的同学做1个科普（请允许我吹1下牛逼）。快速幂可以高效的计算幂运算。如果我们使用循环来计算的话，那末时间复杂度就是 O(n) ，使用快速幂的话就只用 O(log n)。不要小视这么1点点，如果1个问题需要屡次的幂运算的话，可能就会由于这1点小小的变化而超时。

快速幂介绍：

我们1直说快速幂快，那他究竟是在哪里快呢? 如果我们求解 2^k。可以将其表示为

x^n =( (x2)2....)

只要做k次平方运算就能够了，由此我们可以想到，先将n表示为2的幂方次之和

n = 2^k1 + 2^k2 + 2^k3.......

就有

x^n = x^(2^k1) x^(2^k2) x^(2^k3).......

So.快速幂就是这么快。不太明白的可以用笔和纸手动的摹拟1下。

例如： x^22 = x^16・x^4・x^2

快速幂的模板：

typedef long long ll; //注意这里不1定都是long long 有时 int 也行 ll mod_pow(ll x, ll n, ll mod){ ll res = 1; while( n > 0 ){ if( n & 1 ) res = res * x % mod; //n&1其实在这里和 n%2表达的是1个意思 x = x * x % mod; n >>= 1; //n >>= 1这个和 n/=2表达的是1个意思 } return res; }

没看位运算的童鞋，好好回去看看，好多地方都是用这东西

递归版的：

typedef long long ll; ll mod_pow(ll x, ll n, ll mod){ if( n == 0 ) return 1; ll res = mod_pow( x * x % mod, n / 2, mod ); if( n & 1 ) res = res * x % mod; return res; }

下面附上本题的代码：

#include<stdio.h> int mod_pow(int x, int n,int mod){ //快速幂 int res = 1; while( n > 0 ){ if( n & 1 ) res = res * x % mod; x = x * x % mod; n >>= 1; } return res; } int main(){ int m,n; while(scanf("%d%d",&m,&n),n||m) printf("%d ",mod_pow(m,n,1000)); return 0; }

（如有毛病，欢迎指正，转载请注明出处）

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 微信平台――微信公众号简单介绍

下一篇 Eclipse项目发布到Tomcat下被加载两次

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点