问题：求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
快速幂/二分幂的思想还是非常有用的，同时作为简单的算法也值得了解。
递归/迭代的写法在效率上差距不明显，可以采用自己习惯的写法。