【题目描述】
Calculate the an % b where a, b and n are all 32 bit integers.
计算an% b，其中a，b和n都是32位的整数。
【题目链接】
www.lintcode.com/en/problem/fast-power/
【题目解析】
考察整数求模的一些特性，不知道这个特性的话此题一时半会解不出来，本题中利用的关键特性为：
(a * b) % p = ((a % p) * (b % p)) % p
即a 与 b 的乘积模 p 的值等于 a, b 分别模 p 相乘后再模 p 的值，只能帮你到这儿了，不看以下的答案先想想知道此关系后如何解这道题。
首先不太可能先把a^nan具体值求出来，太大了... 所以利用以上求模公式，可以改写a^nan为：
+
a^n = a^{n/2} \cdot a^{n/2} = a^{n/4} \cdot a^{n/4} \cdot a^{n/4} \cdot a^{n/4} \cdot = ...an=an/2⋅an/2=an/4⋅an/4⋅an/4⋅an/4⋅=...
至此递归模型建立。
【参考答案】
