费马小定理（逆元的计算）

费马小定理

如果模数p为质数，且整数a与p互质，则满足：

$a^{p-1} \equiv 1 \pmod{p}$

意义：a的（p - 1）次幂除以p的余数为1。

逆元

1. 模运算可以进行+，-，*，但是不可以进行/（除法），所以就引入了逆元来进行模运算的除法。
2. 若 \(a \times b \equiv 1 \pmod{p}\)，则 \(b\) 是 \(a\) 在模 \(p\) 下的逆元（记作 \(a^{-1}\)）。

用费马小定理推逆元

$a^{p−1} \equiv 1 \pmod{p}$

$a \times a^{p-2} \equiv 1 \pmod{p}$

$ a^{-1} \equiv a^{p-2} \pmod{p}$

然后我们就可以用：$ a^{-1} \equiv a^{p-2} \pmod{p}$ 进行逆元的求解了，p一般取很大的质数。
逆元的求解还要用到快速幂。

代码如下：

typedef long long ll;
const int MOD = 998244353;

// 快速幂：计算 (base^exp) % mod
ll qpow(ll base, ll exp, ll mod) {
    ll res = 1;
    while (exp > 0) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

// 求 a 在模 p 下的逆元（费马小定理）
ll get_inv(ll a, ll p) {
    return qpow(a, p - 2, p);
}