【学习笔记】数论-乘法逆元

板块：数论
前置知识：同余式、费马小定理、裴蜀定理
难度：中等
前置知识一览：

• 同余式：对于式 $a\equiv b(\mathrm{mod}m)$，意义是 $(a-b)|m$，称 $a$ 与 $b$ 对模 $m$ 同余。
• 费马小定理：$a^{p-1}\equiv 1(\mathrm{mod}p)$
• 裴蜀定理：$\forall a,b,\exists x,y,s.t.ax+by=\gcd (a,b)$

冷知识：$\perp$ 符号在数论中表示互质。

什么是乘法逆元-定义

逆元，全称逆元素，是指一个可以取消另一给定元素运算的元素。例如，对于 $ax\times \frac{1}{a}$，由于最后 $x$ 的值 没有发生变化，所以我们称 $a$ 和 $\frac{1}{a}$ 互为逆元。
$$\frac{a}{b}\equiv ax(\mathrm{mod}p),b\perp p$$
对于图示的同余式，我们称 $x$ 是 $b$ 在模 $p$ 意义下的乘法逆元，记作 $b^{-1}$。0没有乘法逆元。

如何求乘法逆元-解决问题

解决乘法逆元的方法有很多，常见的是费马小定理求乘法逆元、扩展欧几里得算法求乘法逆元、线性递推、离线求乘法逆元。
对乘法逆元定义式作如下推导：
由定义式两边同时乘 $b$ 得，$$a\equiv abx(\mathrm{mod}p)$$
两边同时除以 $a$ 得，$$bx\equiv 1(modp)$$
因此， $$\frac{a}{b}\equiv ax(\mathrm{mod}p)⟺bx\equiv 1(\mathrm{mod}p)$$

费马小定理求乘法逆元

时间复杂度 $O(logp)$。
已知费马小定理为 $a^{p-1}\equiv 1(\mathrm{mod}p)$，将 $a^{p-1}$ 拆解为 $a\times a^{p-2}$，再结合乘法逆元推导式 $ax\equiv 1(\mathrm{mod}p)$ 观察可得逆元 $x=a^{p-2}$ ，也就是说，求一个数的乘法逆元，相当于求这个数的 $p-2$ 次方。当然，由于费马小定理的硬性要求，必须满足模数是质数才可以使用该方法。

为了使计算次幂的速度更快，我们可以使用快速幂求解该问题。

• 【模板】费马小定理求乘法逆元

参考代码如下：

#include 
#include 

#define int long long

using namespace std;

int n, p;

int quickm (int a, int b, int p)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        b >>= 1;
        a = a * a % p;
    }
    return res;
}

signed main()
{
    cin >> n >> p;
    for (int i = 1; i <= n; i++)
    {
        cout << quickm(i, p - 2, p) << endl;
    }
    return 0;
}
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

扩展欧几里得算法(exgcd)求乘法逆元

（主要摘抄于参考资料[1]，毕竟也是学习笔记嘛，如果原作者介意可以私信笔者删除）
时间复杂度 $O(logp)$
我们可以受 exgcd 的启发，将乘法逆元式 $ax\equiv 1(\mathrm{mod}p)$ 转化为 $ax+by=1$。
对乘法逆元式作如下推导：
将其转化为： $$ax\mathrm{mod}p=1\mathrm{mod}p$$
移项，得 $$(ax-1)\mathrm{mod}p=0$$
由此得，$$p|(ax-1)$$
设 $ax-1$ 为 $p$ 的 $k$ 倍，即 $ax-1=kp$，继续移项，得
$$ax-kp=1$$
令 $y=-k$，即可转化为 $ax+py=1①$，根据裴蜀定理，我们知道所得方程$①$有解的条件是 $\gcd (a,p)|1$,即 $\gcd (a,p)=1$,$a\perp p$。因此我们不难得出一个结论：$a$ 在模 $p$ 意义下的乘法逆元存在当且仅当 $a,p$ 互质。

因为 $\gcd (a,p)=1$，所以可以直接套用 exgcd 求解，即求解 $ax+py=\gcd (a,p)$， $x$ 就是我们要求的乘法逆元。

参考代码：

#include 
#include 
#include 

using namespace std;

typedef long long LL;

LL a, p, x = 0, y = 0;

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main()
{
    scanf("%lld%lld", &a, &p);
    exgcd(a, p, x, y);
    printf("%lld", (x % p + p) % p); //防负数小妙招 
    return 0;
}
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

线性求逆

如果采用上面方法求解逆元，我们可以再 $O(nlogp)$ 的时间复杂度内，求出 $[1,n](1\le n\le p)$的所有在模质数 $p$ 意义下的乘法逆元，但如果针对下面这题的数据范围时，我们或许需要考虑更快速的方法，于是我们引入了线性求乘法逆元的方法。

• 【模板】数据范围较大的乘法逆元

基于逆元的定义，显然 1 在任意正整数模数意义下的乘法逆元都是它本身，设 $p=ki+r(r<i,1<i<p)$，即 $ki+r$ 是 $p$ 的倍数，转化为同余式得 $ki+r\equiv 0(\mathrm{mod}p)$。作一下推导：
将同余式两边乘 $i^{-1},r^{-1}$，得 $$i^{-1}{r}^{-1}(ki+r)\equiv 0(\mathrm{mod}p)$$
展开得，$$k{r}^{-1}+i^{-1}\equiv 0(\mathrm{mod}p)$$
移项，得 $$i^{-1}\equiv -k{r}^{-1}(\mathrm{mod}p)①$$
由 $p=ki+r$，我们可以推导出 $k=\lfloor \frac{p}{i}\rfloor ,r=p\mathrm{mod}i$，结合①式可得$$i^{-1}\equiv -\lfloor \frac{p}{i}\rfloor \times (p\mathrm{mod}i{)}^{-1}(\mathrm{mod}p)②$$

余数小于除数，所以 $p\mathrm{mod}i<i$，所以 $p\mathrm{mod}i$ 的逆元已经通过递推式②递推出来了，于是我们就可以通过这个式子推出 $i^{-1}$

#include 
#include 

#define int long long

using namespace std;

typedef long long LL;

const int N = 3e6 + 10;

int inv[N], n, p;

int read ()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

signed main()
{
    n = read(), p = read();
    inv[1] = 1;
    printf("1\n");
    for (int i = 2; i <= n; i++)
    {
        inv[i] = (LL)(p - p / i) * inv[p % i] % p;
        printf("%d\n", inv[i]);
    }
    return 0;
}

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
41
42
43