题目：

50. Pow(x, n)

372. 超级次方

1922. 统计好数字的数目

快速幂

快速幂（二进制取幂，平方法），可以在$O(logN)$的时间复杂度内计算出$a^{n}$。

原理：n有$\left \lfloor log_{2} \ n \right \rfloor + 1$个二进制位，所以只用计算$O(logn)$次乘法就可以计算出$a^{n}$。

以计算$3^{13}$​为例：

$3^{13}=3^{(1101)_{2}}=3^{8}\cdot 3^{4}\cdot 3^{1}=3\cdot 81\cdot 6561$​​​

$3^{1}=3$

$3^{2}=(3^{1})^{2}=3^{1}\cdot 3^{1}=9$

$3^{4}=(3^{2})^{2}=3^{2}\cdot 3^{2}=81$

$3^{8}=(3^{4})^{2}=3^{4}\cdot 3^{4}=6561$

static final int MOD = 998244353;
static long quick_pow(long a, long b) {
    long ret = 1;
    // if(b < 0){
    //     b = -b;
    //     a = 1 / a;
    // }
    while (b > 0) {
        if ((b & 1) == 1) ret = ret * a % MOD;
        a = a * a % MOD;
        b >>= 1; // b /= 2;
    }
    return ret % MOD;
}

应用

求逆元

MOD为质数，则i 的逆元就是$\frac{1}{i}=i^{mod-2}\% mod$

用快速幂求$i^{mod-2}$，算法时间复杂度为$O(logN)$

inv(i) = quick_pow(i, MOD-2) % MOD;

计算组合数

组合数计算公式：$C_{a}^{b} = \frac{a!}{(a - b)!\ b!}$​​

利用快速幂可以快速计算出$\frac{1}{(a-b)!}$和$\frac{1}{b!}$，从而快速计算出组合数。

时间复杂度：$O(NlogN)$​

static final int MOD = 998244353;
static final int N = (int) 1e5 + 6;
static long[] fact = new long[N]; //  存储阶乘
static long[] inFact = new long[N]; // 存储阶乘逆元

// 快速幂 a^b
static long quick_pow(long a, long b) {
    long ret = 1;
    while (b > 0) {
        if ((b & 1) == 1) ret = ret * a % MOD;
        a = a * a % MOD;
        b >>= 1; // b /= 2;
    }
    return ret % MOD;
}

// 计算组合数
static long comb(int a, int b) {
    // 初始化
    fact[0] = inFact[0] = 1;
    for (int i = 1; i < N; i++) {
        fact[i] = fact[i-1] * i % MOD;
        inFact[i] = inFact[i-1] * quick_pow(i, MOD-2) % MOD;
    }
    return fact[a] * inFact[a - b] % MOD * inFact[b] % MOD;
}