快速幂 2022-04-05

快速幂（Exponentiation by squaring，平方求幂）是一种简单而有效的小算法，它可以以的时间复杂度计算乘方。快速幂不仅本身非常常见，而且后续很多算法也都会用到快速幂（龟速加也是此思想）。

思想是二分思想：

计算a的n次方，如果n是偶数（不为0），那么就先计算a的n/2次方，然后平方；如果n是奇数，那么就先计算a的n-1次方，再乘上a；递归出口是a的0次方为1。

递归快速幂的思路非常自然，代码也很简单（直接把递归方程翻译成代码即可）：

static int quickMi(int a, int k) {
        int res = 1;
        //a %= mod;   //a可能比较大 a*a 可能会爆int直接进行一次取模；有些地方可以加，有些可以不加
        while (k != 0) {
            //如果是奇数的话
            if ((k & 1) != 0) res = res * a % mod;
            a = a * a % mod;
            k >>= 1;
        }
        return res;
    }