快速幂

所谓快速幂，顾名思义，快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。

熟悉<math.h>或<cmath>头文件的人都会知道函数pow()的作用，没错就是计算一个数的几次幂，其定义如下：

double pow(double x,double y);

它的功能就是计算x的y次幂，返回值就是所求结果。

举个小例子:

以上就是pow()函数的用法了，当然数字可以换成变量。

对于小范围的幂计算，我们可以直接调用pow()函数来解决，但当数据较大时，一是时间较慢，二是容易溢出。（幂运算还是很容易就溢出的，千万不要小看幂运算的威力，可还记得这张图吗？）

2的200次幂，这个数小编已经不会读了，不知道你们怎么样，这个数太大了，以至于C语言的任何基本数据类型都装不下这个数，这里小编用到了python来计算2的200次幂。（一种支持高精度的语言）

因为幂运算的威力太大了，所以幂运算更多的考的是 a的b次幂取余m 的结果。（a^b%m）

---

---

重点来了！！！

快速幂算法用到了分治算法，幂运算的法则相信大家都知道，这里我们要用的只有一条，那就是同底数幂相乘，底数不变，指数相加！！！

我们这里用的是它的逆过程，把一个大的指数拆成若干个较小的指数（两个小的指数相加等于大的指数），然后把它们各自的结果相乘，最终的结果不变。怎么样拆才能尽可能的提高速度呢？答案只有一个，每次拆的子部分尽量相等，这样只需要进行一次计算就好了！

于是，

根据这三种情况我们来写代码就好了，这里同样只写下一个快速幂函数，和pow()一样进行调用就好了！

这样快速幂就写好了。

大家还记得之前提到的 a^b%m 吗？留作思考，开动脑筋想想应该怎么办吧！

---

---