高效的求大数的幂和取余

做TopCoder?SRM 576 D2 L3?题目时，程序有个地方需要对一个数大量求幂并取余，导致程序运行时间很长，看了?Editoral?之后，发现一个超级高效的求幂并取余的算法，之前做System test时，程序运行时间（最慢的测试用例）为500ms左右，使用此方法之后，运行时间直接减为20ms，快了20多倍，所以将此方法记录下来。

算法时间复杂度为 log(n)。

这个算法其实就是 ??数据结构与算法分析 （Weiss 著）??一书中开头的那个递归求幂算法的非递归版，简洁明了。

代码如下：

// Finds x raised to the y-th exponent modulo MOD （即求 x^y % MOD）
    const int MOD = 1e9 + 9;
    int modPow(int x,int y)
  {
    long long res = 1,a = x;
    while (y > 0) {
      if (y & 1) {
        res = (res * a) % MOD;
      }
      a = (a * a) % MOD;
      y >>= 1;
    }
    return static_cast<int> (res);
}