QuickPow

快速幂

求$a^n$可以把它拆成$\underbrace{a \times a\times a \times ...\times a }_{n个a}$ 此算法的时间复杂度为$O(n)$

但它不够快！！！

考虑优化上面的算法

$\because a^{2n}=(a^n)^2$

$\therefore$可以把时间复杂度降到$O(logn)$

//递归方法
long long binpow(long long a, long long b) {
  if (b == 0) return 1;
  long long res = binpow(a, b / 2);
  if (b % 2)
    return res * res * a;
  else
    return res * res;
}

//非递归方法
long long binpow(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}

然后就会注意到一个问题，因为时间复杂度是$O(logn)$，所以$n$最大可以取$1e6$

而$1e6^{1e6}$似乎用高精都会TLE

所以我们可以在过程中取模，像下面这样：

//求a ^ b mod m 的值
long long binpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}