浅谈模质数意义下的乘法逆元

原文链接（更好的阅读体验）

参考文章 www.luogu.org/blog/zyxxs/post-xiao-yi-jiang-tan-qian-tan-sheng-fa-ni-yuan

什么是乘法逆元

若整数 \(b,m\) 互质，并且 \(b|a\) ，若存在一个整数 \(x\) ，使得 \(a / b \equiv a \ast x (mod \text{ } m)\) ，称 \(x\) 为 \(b\) 的模 \(m\) 乘法逆元 。

乘法逆元的用处

有时候，我们需要求 \(a/b \text{ } mod \text{ } p\) ，用朴素的方法，我们只能在 \(a\) 上不断加 \(p\) ，直到它能被 bb 整除为止，当 \(a,b,p\) 都很大的时候，自然是凉凉了。这时，我们就可以用逆元方便的求解了。

乘法逆元的求法

进入到了本文最关键的部分，如何求乘法逆元?

费马小定理

费马小定理：当 \(p\) 是质数的时候，$a^{p-1} \equiv 1 (mod \text{ } p) $

那么将 \(a^{p-1}\) 拆开来，就得到了 \(a \ast a^{p-2} \equiv (mod \text{ } p)\)

所以， \(a^{p-2}\) 就是 \(a\) 模 \(p\) 意义下的乘法逆元。

缺点：用快速幂计算，当 \(p\) 比较大的时候，速度比较慢。

代码：

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;

ll n, p;

ll ksm(ll a, ll b)
{
    ll ans = 1;
    for (; b; b >>= 1) {
        if (b & 1)
            ans = ans * a % p;
        a = a * a % p;
    }
    return ans;
}

int main()
{
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    cin >> n >> p;
    for (int i = 1; i <= n; ++i) {
        printf("%lld\n", ksm(i, p - 2));
    }
    return 0;
}

扩展欧几里得算法

求 \(a \ast x \equiv 1 (mod \text{ } m)\) 的解 \(inv(x)\) ，等价于求解 \(a \ast x + b \ast y =1\) 。用扩展欧几里得算法求出一组特解 \(x_0, y_0\) ，则 \(x_0\) 是原方程的一个解，而方程的通解则为所有模 \(m\) 与 \(x_0\) 同余的整数，通过取模操作把解的范围移动到 \(1～p\) 之间即可。

代码：

#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;

ll n, p;

void exgcd(ll a, ll b, ll& x, ll& y)
{
    if (b == 0) {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, x, y);
    ll z = x;
    x = y, y = z - y * (a / b);
    return;
}

int main()
{
    cin >> n >> p;
    for (int i = 1; i <= n; ++i) {
        ll x, y;
        exgcd(i, p, x, y);
        x = (x % p + p) % p;
        cout << x << endl;
    }
    return 0;
}

线性递推（可以求多个）

这是一个神奇的过程……

假设我们现在要求 \(k\) 的乘法逆元，

令 \(a \ast k + b = p\)

\[b \ast inv(b) \equiv 1 (mod \text{ } p)\]

把 \(b=p-a\ast k\) 代入，可以得到

\[(p-ak)\ast inv(b) \equiv 1 (mod \text{ } p)\]

那么

\[p \ast inv(b) - a \ast k \ast inv(b) \equiv 1 (mod \text{ } p)\]

在 \((mod \text{ } p)\) 的意义下， \(p \equiv 0 (mod \text{ } p)\) ，所以 \(p \ast inv(b)\) 可以直接去掉

\[-a \ast k \ast inv(b) \equiv 1 (mod \text{ } p)\]

观察 \(a \ast k + b = p\) 可以发现， \(a=\lfloor p/k \rfloor\) ， \(b=p \mod k\)

\[-(p/k) \ast inv(p \text{ } mod \text{ } k) \ast k \equiv 1 (mod \text{ } p)\]

即

\[-(p/k) \ast inv(p \text{ } mod \text{ } k) \equiv inv(k) (mod \text{ } p)\]

这样，我们就得了递推式，在实际的代码实现中得加上 \(p\) 来去掉负号，也就是

\[(p-p/k) \ast inv(p \text{ } mod \text{ } k) \equiv inv(k) (mod \text{ } p)\]

代码：

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
ll n, p, inv[maxn];

int main()
{
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    cin >> n >> p;

    inv[1] = 1;
    for (int i = 2; i <= n; ++i)
        inv[i] = (ll)(p - p / i) * inv[p % i] % p;
    for (int i = 1; i <= n; ++i)
        printf("%lld\n", inv[i]);
    return 0;
}