hdu2035 人见人爱A^B(快速幂取模)

题目链接: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;
}

(如有毛病,欢迎指正,转载请注明出处)

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » hdu2035 人见人爱A^B(快速幂取模)

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡