快速幂和快速幂取模

首先，快速幂的目的就是做到快速求幂，假设我们要求 a^b，按照朴素算法就是把 a 连乘 b 次，这样一来时间复杂度是 O(b)也即是 O(n)级别，快速幂能做到 O(logn)，快了好多好多。它的原理如下：

假设我们要求 a^b，那么其实 b 是可以拆成二进制的，该二进制数第 i 位的权为 2^(i-1)

例如当 b==11 时,a^11=a^(2^0+2^1+2^3)，11 的二进制是 1011，11 = 2^3×1 + 2^2×0 + 2^1×1 + 2^0×1，

因此，我们将 a^11 转化为算a^(2^0)a^(2^1)a^(2^3)，也就是a^1 _ a^2 _ a^8.

由于是二进制，很自然地想到用位运算这个强大的工具：&和»。 &运算通常用于二进制取位操作，例如一个数 & 1 的结果就是取二进制的最末位。还可以判断奇偶 x&1==0 为偶，x&1==1 为奇。 »运算比较单纯,二进制去掉最后一位。具体看代码。

快速幂算法：

int pow2(int a, int b)
{
  int ans = 1;
  while (b)
  {
    if (b & 1)
      ans *= a; //末位是1
    a *= a;
    b = b >> 1;
  }
  return ans;
}

快速幂模运算根据(a^b) mod c=(a mod c)^b mod c

快速幂取模：

int PowerMod(int a, int b, int c)
{
  int ans = 1;
  a = a % c;
  while (b)
  {
    if (b % 2 == 1)
      ans = (ans * a) % c;
    b = b / 2;
    a = (a * a) % c;
  }
  return ans;
}