题目大意：输入b,p,k的值，求b^p mod k 的值。 其中b,p,k*k 为长整形正数。

输入

输出

样例输入

2 10 9

样例输出

2^10 mod 9=7

解题思路

b^p mod k，b^p会超过基本数据类型，但可以通过取模避免使用高精度。然而p为长整型，如果p=1e9，乘1e9次，就会超时。我们可以考虑用log级别的算法。

如果p是偶数，那么b^p = b^(2*p/2) = (b^2) ^ (p/2)，这样计算p次就转化成p/2次了；如果p是奇数，b^p = b ^ (1+p-1) = b * b ^ (p-1)，次幂就转化成偶数了。就这样，偶数可以减半，奇数1次可以转成偶数，不管是奇数还是偶数，都可以在2次以内将次幂减半。就这样不停/2和-1，b最终会变为0，因此结束条件为b=0，0次幂返回1。时间复杂度O(log(p))。

程序实现