问题：求a^b % m，即a的b次方对m取余的结果。

只要学过C语言的循环就可以写出最简单的朴素版本：

朴素版

时间复杂度O（b），空间复杂度达到了惊人的O（a^b）的指数级。

考虑问题规模：a <(10 ^ 9)， b <(10 ^ 6)，m <(10 ^ 9)。

问题出现了：这样的算法在求a的b次幂的时候就极其容易溢出，即便用long long也是如此。

我们有取模运算的运算法则：
(a * b) % p = (a % p * b % p) % p

在这里不加证明的使用。

所以在这个前提下，我们可以在求a的b次幂的同时，每次对m进行%操作，这样可以使得ans不会越界。

根据思想可以写出以下代码：

改进版

时间复杂度O（b），空间复杂度为的O（max（a，m）），此时溢出的问题是得到了解决。

但如果考虑问题规模：a <(10 ^ 9)， b <(10 ^ 18)，m <(10 ^ 9)，这样显然又无法满足需要了。

快速幂

这时候引入快速幂，它基于二分的思想，所以也称为二分幂。

不难注意到这样的事实：求a^b的过程中，b只有两种情况：奇数或偶数。

若b为偶数，则a^b = a^(b/2) * a^(b/2)。

若b为奇数，则a^b = a * a ^ (b-1)。且从下一次开始，b必然为偶数的情况。

基于以上思想就可以成功把求幂过程的复杂度降为（logb）。这样就可以满足原规模的数据了。

根据思想写出以下递归版本代码：

递归版：

我们也可以进一步写出迭代版本的代码（From算法笔记）：

迭代版：

两组测试

1：10000 ^ 500000000 mod 71

朴素版已由于溢出导致结果错误，而优化版虽然能得出正确答案，但耗时相当长，快速幂的两种实现几乎没有任何耗时。

2：1003 ^ 9223372036854775807 mod 71

快速幂/二分幂的思想还是非常有用的，同时作为简单的算法也值得了解。

递归/迭代的写法在效率上差距不明显，可以采用自己习惯的写法。