起因
刷LeetCode时突然碰到了这种求大指数的问题，这种将理论转化为工程的方式彻底吸引了我，有必要把学习过程记录下来。
目标
计算 $a^b \ mod \ c$ 的值
为什么要在模 $c$ 下计算？
由于指数函数快速增长的性质，$a, b$ 稍微大一点，$a^b$ 就很容易超出编程语言的数据范围，因此往往只能考虑在模 $c$ 下的值，这是一种无奈之举。
快速幂算法
首先假设 $a^b$ 的值不超过数值范围(long)，然后考虑计算其值。一种平凡的做法是在循环内依次累乘 $a$，时间复杂度为 $O(b)$；除此之外，还有一种在 $log(b)$ 下的快速幂算法，十分高效。
已知对于任何的正整数 $b\in\mathbb{Z_+}$，都有 $$b=\sum_{i=0}^{\infty} b_i2^i \ (b_i=0\ or\ 1)$$
举个例子，$15=2^3+2^2+2^1+2^0$。
进而，$$a^b=a^{\sum b_i2^i}=\prod a^{b_i2^i}$$
举例，$a^{15}=a^{2^0}a^{2^1}a^{2^2}a^{2^3}=a^{1}a^{2}a^{4}a^{8}$，要注意到$b_i$的取值不同。显然，$a^{8}$可由$a^{4}$直接平方获得。
