递推的应用——快速幂
让你计算 你会怎么算？
是不是这样：
long long ans = 1;
for(int i = 0; i < 98; i++){
ans *= 6;
}
好家伙，用了九十八次乘法。
但如果把 看成是 的平方，再把 看作是 的平方除以6……这样不就可以大大减少算法的复杂度了吗？
显然，使用递归的算法是最简单的实现方式。
当次数为1，返回底数
当次数为偶数，调用并返回一个底数不变，次数除以二的幂的平方
当次数为奇数，调用并返回一个底数不变，次数除以二的幂的平方除以2
代码实现
long long x1,k11;
int pow(long long k,long long x){
if(k == 1){
return x;
}else if(k % 2 == 0){
long long a = pow(k/2,x);
return a*a;
}else if(k % 2 == 1){
long long a = pow(k/2,x);
return a*a/x;
}
}
int main(){
cin >> x1 >> k11;
cout << pow(x1,k11);
return 0;
}