由于数据规模太大，单纯地使用循环一定会发生溢出，即使用long long。
这里要使用快速幂的做法，它基于二分思想，也被称为二分幂。快速幂基于以下事实：
如果 b 是奇数， 那么有 ;如果 b 是偶数， 那么有 ;显然， b 是奇数的情况总可以在下一步转换为 b 是偶数的情况， 而 b 是偶数的情况总可以在下一步转换为 b 是奇数的情况。
举例， 如需求 :
对于 来说 ， = 对于 来说 ， 对于 来说 ， 对于 来说 ， 对于 来说 ， = 1, 然后从下往上依次回退计算即可 。这显然是递归的思想， 于是得到快速幂的递归写法， 时间复杂度 O(logb) ：
typedef long long LL; LL binaryPow(LL a, LL b, LL m){ if(b == 0) return 1; if(b % 2 == 1) return a * binaryPow(a, b - 1, m) % m; else{ LL mul = binaryPow(a, b / 2, m); return mul * mul % m; } }PS：
如果初始时 a 有可能大于等于 m， 那么需要在进入函数前就让 a 对 m 取模。如果 m 为 1， 可以直接在函数外部特判为 0， 不需要进入函数来计算 （因为任何正数对 1 取模一定为 0 ）。