乘法逆元

1. 逆元的定义

如果一个线性同余方程$ax \equiv 1 (mod\ b)$，则称$x$为$a\ mod\ b$的逆元，记作$a^{-1}$。

模运算规则与基本四则运算类似，但是除法例外。在ACM竞赛中，除法取模的运算要用到求逆元，从而得到$(a / b) \% c = (a * x) \% c$

证明：已知$(b * x) \% c = 1$，假设$(a / b) \% c = y_1, (a * x) \% c = y_2$

则

$a / b = k_1*c + y_1\quad(1)$
$a*x = k_2 * c + y_2\quad(2)$
$(1) -(2)$$\quad \rightarrow \quad a/b - a*x = (k_1 - k_2)*c + (y_1 - y_2)$
左右同时乘以b $\quad \rightarrow \quad$ $a - a * x * b = k * c * b + (y1 - y2) * b$
左右模上c $\quad \rightarrow \quad (y1 - y2) * b \% c = 0$
因为$b \neq 0$, 所以$y_1 = y_2$

2. 求逆元

费马小定理，若p为素数，且$gcd(a, p) = 1$，则$a^{p - 1} \equiv 1 (mod\ p)$

证明：

构造一个序列$A={1, 2, 3, \dots p - 1}$，这个序列有如下的性质:
$\mathop{\Pi}\limits_{i = 1}^{n}A_i = \mathop{\Pi}\limits_{i = 1}^{n}(A_i \times a)$
对于任意$i, j \in n $，$(A_i * a )\% p \neq (A_j * a )\% p$，因为$(A_i - A_j) * a \% p = 0$，则$A_i - A_j = 0$
因此$(p - 1)! \equiv (p - 1)! * a^{p - 1}\ (mod\ p) \quad \rightarrow a^{p - 1} \equiv 1 \ mod(\ p)$

2.1 扩展欧几里得算法

扩展欧几里得算法

求解同余方程$ax \equiv 1 (mod\ b)$的最小整数解

假设采用扩展欧几里得算法求得一组$x_0, y_0$满足$ax_0 +by_0 = gcd(a, b)$，则该方程的任意解可以表示为$x = x_0 + bt, y = y_0-at$，对于任意t均成立，最小整数解可以表示为$x = ((x_0\ mod\ b) + b) mod\ b$

2.2快速幂算法

根据费马小定理，$1 \equiv a^{p -1} (mod\ p)$，因此$x = a^{p - 2}$，可以采用快速幂算法进行计算。

ll qpow(long long a, long long b) {
    ll ret = 1;
    while (b) {
        if (b & 1) {
            ret = (ret * a) % mod;
        }
        b >>= 1;
        a = (a * a) % mod;
    }
    return ret;
}

2.3 线性求逆元

求出$1, 2, \dots, n$中每个数关于p的逆元。

显然$1{-1} \equiv 1 (mod\ p)$
令$k = \lfloor\frac{p}{i} \rfloor, j = p\ mod\ i$, 因此有$p = ki + j$，在模p的意义下就有$ki + j \equiv 0\ (mod\ p)$
左右同乘以$i^{-1}, j^{-1}$，有$kj^{-1} + i^{-1}=0$
$i^{-1}=-kj^{-1} = (p - k)j^{-1}$

static const expr mod = 1e9 + 7;
ll fac[N], R[N], inv[N];
fac[0] = fac[1] = R[0] = R[1] = inv[0] = inv[1] = 1;
for (int i = 2; i <= n; ++i) {
	fac[i] = 1LL * fac[i - 1] * i % mod;
    inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
    R[i] = 1LL * R[i - 1] * inv[i] % mod;
}

ll comb(int n, int m) {
	if (n < m) return 0;
	return 1LL * fac[n] * R[m] % mod * R[n - m] % mod;
}

2.4 线性求任意n个数的逆元

using LL = long long;
static constexpr LL mod = 99997867;
static constexpr int N = 1000005;
LL fac[N], rf[N];

LL qpow(LL a, LL b) {
    LL ret = 1;
    while (b) {
        if (b & 1) {
            ret = ret * a % mod;
        }
        b >>= 1;
        a = a * a % mod;
    }
    return ret;
}

void init() {
    fac[0] = 1;
    for (int i = 1; i < N; ++i) {
        fac[i] = fac[i - 1] * i % mod;
    }
    rf[N - 1] = qpow(fac[N - 1], mod - 2);
    for (int i = N - 2; i >= 0; --i) {
        rf[i] = rf[i + 1] * (i + 1) % mod; 
    }
}

LL comb(int n, int m) {
    if (n < m || m < 0) return 0;
    return fac[n] * rf[n - m] % mod * rf[m] % mod;
}