快速幂模板讲解和快速幂代码

在讲解快速幂之前，让我们先来思考一个问题：7的10次方，怎样算比较快？ 方法1：最朴素的想法，7*7=49，49*7=343，... 一步一步算，共进行了9次乘法。 这样算无疑太慢了，尤其对计算机的CPU而言，每次运算只乘上一个个位数，无疑太屈才了。这时我们想到，也许可以拆分问题。 方法2：先算7的5次方，即7*7*7*7*7，再算它的平方，共进行了5次乘法。 但这并不是最优解，因为对于“7的5次方”，我们仍然可以拆分问题。 方法3：先算7*7得49，则7的5次方为49*49*7，再算它的平方，共进行了4次乘法。 模仿这样的过程，我们得到一个在O(log n)时间内计算出幂的算法，也就是快速幂。 计算a的n次方，如果n是偶数（不为0），那么就先计算a的n/2次方，然后平方；如果n是奇数，那么就先计算a的n-1次方，再乘上a；递归出口是a的0次方为1。 递归快速幂的思路非常自然，代码也很简单（直接把递归方程翻译成代码即可） 这次的讲解就到这里了，希望大家对快速幂能有所了解，快速幂还包涵矩阵快速幂，快速幂的代码是需要背的，如果要熟练的话就只能多背！