快速幂

快速幂（Exponentiation by squaring，平方求幂）是一种简单而有效的小算法，它可以以[公式]的时间复杂度计算乘方。

方法1：最朴素的想法，7*7=49，49*7=343，... 一步一步算，共进行了9次乘法。

方法2：先算7的5次方，即7*7*7*7*7，再算它的平方，共进行了5次乘法。

方法3：先算7*7得49，则7的5次方为49*49*7，再算它的平方，共进行了4次乘法。

7的10次方，怎样算比较快？

思考

二分法，可以得到一个递归方程：

计算a的n次方：如果n是偶数（不为0），那么就先计算a的n/2次方，然后平方；如果n是奇数，那么就先计算a的n-1次方，再乘上a；递归出口是a的0次方为1。

思路

实现

递归虽然简洁，但会产生额外的空间开销。

优化

递归快速幂

我们把10写成二进制的形式，也就是 （1010）。

我们很自然地想到可以把它拆分为（1000）+（10）

实际上，对于任意的整数，我们都可以把它拆成若干个（10....）的形式相乘。

现在我们要计算 （1010） ，可以怎么做？

非递归快速幂

取模的运算不会干涉乘法运算，因此我们只需要在计算的过程中取模即可

模意义下取幂: 计算 x^k % n.

应用

快速幂