快速幂 手算到机算 入门
总目录：从手算到机算 算法竞赛入门篇
计算2^20,采用快速幂的手算过程如下：
以下计算过程一直保持a*b=2^20
初始状态：a=2^20 b=1
第一次运算：a=(2^2)^10=4^10 b=1
第二次运算：a=(4^2)^5=16^5 b=1
第三次运算：a=16^4 b=16; a=(16^2)^2=256^2 b=16
第四次运算：a=(256^2)^1=65536^1 b=16;
第五次运算：a=(65536)^0=1 b=16*65536=1048576;
输出b的结果，就是2^20=1048576
机算过程如下：
输入:
2 20
表示求2^20
#include <bits/stdc++.h>
int a,b;
int quick_pow(int a,int b){
int ret=1;
while(b){
if(b&1)ret=ret*a;
a=a*a;
b>>=1;
}
return ret;
}
int main(){
scanf("%d%d",&a,&b);
printf("%d\n",quick_pow(a,b));
return 0;
}
练手：
洛谷 P1226 【模板】快速幂||取余运算
洛谷 P1965 转圈游戏
洛谷 P3197 [HNOI2008]越狱
解答：
洛谷 P1226 【模板】快速幂||取余运算
AC代码如下：
#include <bits/stdc++.h>
#define LL long long
LL b,p,k;
LL quick_pow(LL a,LL b,LL mod){
LL ret=1;
while(b){
if(b&1)ret=ret*a%mod;
a=a*a%mod;
b>>=1;
}
return ret%mod;//此处对应2^0%1=0的情况
}
int main(){
scanf("%lld%lld%lld",&b,&p,&k);
printf("%lld^%lld mod %lld=%lld\n",b,p,k,quick_pow(b,p,k));
return 0;
}
洛谷 P1965 转圈游戏
洛谷 P3197 [HNOI2008]越狱