在 int32 的存储条件下，大数计算乘法，可能会超出数值范围，导致返回值错误

循环求余法

把指数操作转换成一次次的乘法，每次相乘就取以此余数，使得数值不超过范围

  1. int remainder(int x, int a, int p)
  2. {
  3.     int rem = 1;
  4.     while (a--)
  5.     {
  6.         rem = (rem * x) % p;
  7.     }
  8.     return rem;
  9. }

快速幂取余

用快速幂的方法时间复杂度可以达到O(logn)
思想: X2 = x * x, X4 = X2 * X2, X8 = X4 * X4

int fastPower(long long base, long long power, int p) {
    long long result = 1;
    while (power > 0) {
        if (power & 1) {
            result = result * base % p;
        }
        power = power >>= 1;
        base = (base * base) % p;
    }
    return (int)result;
}

参考文章: http://t.csdn.cn/N9SMC