快速幂(快速求幂指数)

介绍

假设我们要求(2^10)%1000，我们得循环求10次，但如果次数太多了那么就会TLE了。

参考链接

快速幂求幂次方

这里我们可以看出来，如果指数是奇数那就直接乘拆出来的那么数就行了。偶数就一直拆，最后肯定会变成奇数的。
这里我们要注意两点

• res是取1而不是0
• a, b, p, res都要开long long
  

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(log2 n)。
就是每次先将原来的式子改变一下。

• 如果指数是偶数
  就分成一个数的平方，然后指数除以2。
• 如果指数是奇数
  就拆出来一个数，然后指数就变成偶数了，就按指数是偶数的做了。
• 和上面的区别就是多了个取模。

int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}