模意义下的乘法逆元

自学逆元...

定义

OI 中常用“逆元”作“模意义下的乘法逆元”。 \[ ax\equiv 1 \pmod b \] 则 \(x\) 为模 \(b\) 意义下的 \(a\) 的逆元，记作 \(a^{-1}\) 。
通俗来讲，\(a\cdot a^{-1} \bmod b = 1\)

用途

先讲用途再说求法？

对于 \(\frac ab\)，想要对结果取模，但是实际上 \(\frac ab \bmod p \neq \frac {a\bmod p}{b \bmod p}\)
难道没有办法了吗？
并不是。

设 \(b^{-1}\) 为 \(b \bmod p\) 意义下的逆元，则有 \[ \frac ab \bmod p = a\cdot b^{-1} \] ## 求单个逆元

扩展欧几里得算法

此法相对于快速幂来说，限制少，常数小，因此比较优，不再写快速幂法。实际上是我不会快速幂法

容易发现乘法逆元定义式就是一个普普通通的同余方程
于是可以轻松使用扩欧求解
详见 同余方程与二元一次不定方程

线性求逆元

由于线性求任意多个数逆元过于简单，所以直接记录这个解法。

考虑逆元的定义，容易想到对于 \(a^{-1}b^{-1}\) 来说，乘 \(a\) 即可消除 \(a^{-1}\) 的影响，即 \[ a\cdot a^{-1}b^{-1} \bmod p = (a\cdot a^{-1} \bmod p)b^{-1} = b^{-1} \] 与此同时，两个数积的逆元等于两个数逆元的积
证明： \[ \begin{aligned} aa^{-1} \bmod p &= 1\newline bb^{-1} \bmod p &= 1\newline aa^{-1} \cdot bb^{-1} \bmod p &= 1 \newline ab \cdot a^{-1}b^{-1} \bmod p &= 1 \newline \therefore (ab)^{-1} = a^{-1}b^{-1} \end{aligned} \] 因此对于任意数列 \(a_1 \dots a_n\) ，可以先求出其前缀积 \(s_i\) ，然后利用扩展欧几里得求累积的逆元 \(f_n = s_n^{-1}\)，然后从后往前线性复杂度求出前缀积的逆元 \(f_{i-1} = f_ia_i \bmod p\) ，最后从前往后扫一遍求出每个数的逆元 \(inv_i = s_{i-1}f_i\) 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

i32 tmp;

void exgcd(i32 a, i32 b, i32& x, i64& y) {
    if (!b) {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, x, y);
    tmp = x;
    x = y;
    y = tmp - (a / b) * y;
}

#define N 5000001

i32 a[N], s[N], f[N];
i64 n, p, k, ans, ktmp, y;

int main() {
    read(n, p, k);
    s[0] = 1;
    for (i32 i = 1; i <= n; ++i)
        read(a[i]), s[i] = s[i - 1] % p * a[i] % p;
    exgcd(s[n], p, f[n], y);
    // write(p, '\n');
    for (i32 i = n - 1; i; --i) {
        f[i] = f[i + 1] % p * a[i + 1] % p;
    }
    f[1] %= p;
    ans = k * f[1] % p;
    ktmp = k % p;
    for (i32 i = 2; i <= n; ++i) {
        f[i] = s[i - 1] % p * f[i] % p;
        ktmp = (ktmp * k) % p;
        ans = ((ans % p + ktmp * f[i]) % p + p) % p;
    }
    write(ans, '\n');
    
    return 0;
}