hdu2035 人见人爱A^B（快速幂取模）
发布时间：2020-12-13 20:46:15 所属栏目：PHP教程 来源：网络整理
导读：题目链接： hdu 2035 人见人爱A^B 很早的时候做的1道题了，今天想一想把他翻了出来，写篇文章来为不知道快速幂的同学做1个科普（请允许我吹1下牛 ）。快速幂可以高效的计算幂运算。如果我们使用循环来计算的话，那末时间复杂度就是 O(n) ，使用快速幂的话就
|
题目链接：hdu 2035 人见人爱A^B 很早的时候做的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 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;
} （如有毛病，欢迎指正，转载请注明出处） （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
）。快速幂可以高效的计算幂运算。如果我们使用循环来计算的话，那末时间复杂度就是 O(n) ，使用快速幂的话就只用 O(log n)。不要小视这么1点点，如果1个问题需要屡次 的 幂运算的话，可能就会由于这1点小小的变化而超时。