逆元

费马小定理和逆元

在模运算中，逆元是一个非常重要的概念。如果 aa 和 MODMOD 互质（即它们的最大公约数是 1），那么 aa 在模 MODMOD 下的逆元 bb 满足：

ab≡1(modMOD)ab \equiv 1 \pmod{MOD}

逆元实质上是乘法操作的“撤销”。在模 MODMOD 算术中，逆元使我们能够通过乘以逆元来“消除”一个数的影响，从而简化计算。

费马小定理告诉我们如何快速找到逆元，费马小定理是关于素数的一个定理，它提供了一种快速计算幂模的方法。如果 pp 是一个素数，且 aa 不是 pp 的倍数，那么 ap−1a^{p-1} 被 pp 除的余数总是 1。用数学语言来描述就是：

ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}

a∗ap−2≡1(modp)a * a^{p-2} \equiv 1 \pmod{p}

a≡1/ap−2(modp)a \equiv 1 / a^{p-2} \pmod{p}

x/a≡x∗ap−2(modp)x / a \equiv x * a^{p-2} \pmod{p}

所以要除以a的时候，可以用乘以a^(p-2)来替换

称作 aa 在模 pp 下的逆元是 ap−2a^{p-2} 模 pp

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private static final int MOD = (int)1e9+7;
private static final int MX = 3001; // MAX_N + MAX_M = 2000 + 1000 = 3000
private static final long[] F = new long[MX]; // f[i] = i!
private static final long[] INV_F = new long[MX]; // inv_f[i] = i!^-1
static {
    F[0] = 1;
    for (int i = 1; i < MX; i++) {
        F[i] = F[i - 1] * i % MOD;  // 递推计算阶乘
    }
    INV_F[MX - 1] = pow(F[MX - 1], MOD - 2);  // 利用费马小定理计算逆元
    for (int i = MX - 1; i > 0; i--) {
        INV_F[i - 1] = INV_F[i] * i % MOD;  // 递推前面阶乘项的逆元
    }
}
private static long pow(long x, int n) {  // 快速幂
    long res = 1;
    for (; n > 0; n /= 2) {
        if (n % 2 > 0) {
            res = res * x % MOD;
        }
        x = x * x % MOD;
    }
    return res;
}

快速计算组合数结果（模取）

在计算组合数结果需要模取一个素数的情况下，可以利用逆元快速计算组合数

1
2
3
private long comb(int n, int m) {  // 计算组合数
    return F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD;
}

题解