快速幂 手算到機算 入門
總目錄：從手算到機算 算法競賽入門篇
計算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]越獄