请享用美味的快速幂算法-通俗易懂版
一、算法整体思路第1步
按照最直接、最好理解的方式看，2的n次幂是n个2相乘，即有如下公式
https://img2023.cnblogs.com/blog/2425112/202307/2425112-20230721095026649-19901958.png
例如：
https://img2023.cnblogs.com/blog/2425112/202307/2425112-20230721095111691-1204606539.png
第2步
然而为了节省大量时间，通过简单的思考和严格数学推理，我们不难理解以下结论：
1.偶数幂的情况:
通过幂函数运算法则，有2n=（2n/2）2，即有如下等式：
https://img2023.cnblogs.com/blog/2425112/202307/2425112-20230721100708206-738262179.png
例如24 的计算过程如下所示：
https://img2023.cnblogs.com/blog/2425112/202307/2425112-20230721101451736-648296080.png
得到上面的表达式后，22是不是可以继续按照这个思想分解下去？of course！现在只是举了一个4次方的例子，我们可以从此得到启发，发现求n次幂最终可以归结为不断的重复这个分解的一个过程，直到幂不能分解（幂为0了）才停下来。
由此，上述过程可以描述为一个递归过程，递归基（递归结束条件）为”幂等于0“。得到以下递归表达式：
https://img2023.cnblogs.com/blog/2425112/202307/2425112-20230721111418193-1089234148.png
小插叙：
解释第二种情况前，有必要说明以下内容，这也是为什么第二种情况存在的原因：
如果n是奇数，我们知道，在计算机中，n/2会舍去小数，这样如果继续按照上述第一步的方法分解，逆推回去，会发现最终得到的幂是n-1；不信，且看下例
https://img2023.cnblogs.com/blog/2425112/202307/2425112-20230721105532043-47517452.png
2.奇数幂的情况：
好了，现在可以引出第二种情况，就是奇数幂的情况。我们要求得奇数幂的结果，可以从继续步骤1,即按照偶数幂的求法求出最终结果，再附加一个条件是，什么条件呢？
就是在原来的结果上乘上一个2，原因我相信在插叙中已经说的很明白了，它少了1次幂，现在是在补上这一次幂，即：
https://img2023.cnblogs.com/blog/2425112/202307/2425112-20230721112218248-519099260.png
3.最终递归表达式
那么到现在，我们可以写出完整的递归表达式了，在偶数幂的递归条件下，附加奇数幂的条件即可，即：
https://img2023.cnblogs.com/blog/2425112/202307/2425112-20230721112500791-1363721165.png
第3步
我们现在对于快速幂的求解思路应当是已经十分清晰了，现在我们来写递归函数(C++):
long long int fastpower(int n){
if (n == 0)//递归基
return 1;
else if (n % 2 == 0)//偶数幂的情况
return square(fastpower(n / 2));
else//奇数幂的情况
return square(fastpower(n / 2)) * 2;
}
long long int square(long long int t){
return t * t;
}
二、上刑
everybody，现在我们已经完全理清了思路，接下来要把它整成代码吧！
#includeusing namespace std;long long int fastpower(int n);//求解快速幂long long int square(long long int t);//平方int main(void){ int n; cin >> n;//输入幂 cout
页:
[1]