快速幂算法例子:
$5^{16}=25^8=625^4=390625^2=152 587 890 625$ $3^{20}=9^{10}=81^5=8181^4=816561^2=81*43046721=3 486 784 401$
利用二分法能大大加快了求解速度
代码:
int Power(int base,int index){
int result=1;
while(index!=0){
if(index%2 == 1) result =result*base;
base = base* base;
index/=2;
}
return result;
}
快速幂求余:
$3^{20}%4=(9%4)^{10}%4=5^{10}%4=(25%4)^5%4=1^5%4 Rightarrow result=(1*1)%4=1$
$6^{13}%7 Rightarrow result =(16)%7=6,(36%7)^6%7=(1%7)^3 Rightarrow result=(61)%7=6,1%7….result=6$
int PowerMod(int base, int index, int mod){
int result = 1;
base = base % mod;
while(index!=0){
if(index%2 == 1) result =(result*base)%mod;
base = (base * base) % mod;
index /= 2;
}
return result;
}
近期评论