1. 简介

乘法逆元，相同于在模除法做像倒数一样的操作。

比如：

对于模$5:4$的逆元是什么

$$\frac{1}{4}\equiv v(\mathrm{mod}5)$$
也就是在模中除$4$，相当于乘上一个什么样的数。
$$4v\equiv 1(\mathrm{mod}5)$$

我们的目的是将模运算中要进行的除操作转换成乘。

根据裴蜀定理我们知道，只有当$\gcd (4,5)=1$时，

$v$才可能有解，也就是有逆元。

因此我们可以用扩展欧几里得来求逆元。

下面的代码以luoguo p3811为例。

2. 扩展欧几里得求逆元

这里直接用扩展欧几里得就可以了，只要$\gcd (a,m)=1$就可以了。

也就是对应着$x$的值，不过$x$的值有可能是负的，所以需要加上$m$。

#include <iostream>
#include <vector>int exgcd(int a, int b, int &x, int &y) {if (0 == b) {x = 1;y = 0;return a;}// int x_1;// int y_1;// int d = exgcd( b,a %b, x_1, y_1);// x = y_1;// y = x_1 - (a / b) * y_1;int d = exgcd( b, a % b, y, x);y -= (a / b) * x;return d;
}int main()
{int n;int p;std::cin >> n >> p;std::vector<int> mem(p, 0);int rev,y;for(int i = 1;i <= n;i++) {if ( i < p) {exgcd( i, p, rev, y);if (rev < 0)rev += p;mem[i] = rev;}std::cout << mem[i % p] << '\n';}return 0;
}

3. 费马小定理求乘法逆元

根据费马小定理我们有：

$$\begin{gathered} pisprime \\ \gcd (a,p)=1\Rightarrow \\ p\mid a^{p-1}-1\Rightarrow a^{p-1}\equiv 1(\mathrm{mod}p) \end{gathered}$$

因此此时有：
$$a^{p-2}a\equiv 1(\mathrm{mod}p)$$

$a$的乘法逆元此时为$a^{p-2}$。

需要注意的是我们的模数需要是质数，才能用。

#include <cstdio>
#include <vector>using ll = long long;ll fpow(ll base, ll cnt, ll mod) {if (1 == base)return 1;ll tmp = base;ll ans = 1;while (cnt) {if (cnt & 1) ans  = (ans * tmp) % mod;tmp  = (tmp * tmp) % mod;cnt >>= 1;}return ans;
}int main()
{long long  n;long long p;scanf("%lld%lld", &n, &p);for (int i = 1;i <= n; i++) {printf("%lld\n", fpow(i, p - 2, p));}return 0;
}

4. 积性函数求乘法逆元

我们容易证明求乘法逆元是积性函数

$$\begin{gathered} a\times inv(a)\equiv 1(\mathrm{mod}p) \\ b\times inv(v)\equiv 1(\mathrm{mod}p) \\ ab\times inv(b)inv(a)\equiv 1(\mathrm{mod}p) \\ inv(ab)=inv(a)inv(b) \end{gathered}$$

递推式
$$\begin{array}{rl}p& =ki+r\\ ki+r& \equiv 0(\mathrm{mod}p)\\ -ki& \equiv r(\mathrm{mod}p)\\ (p-k)i& \equiv r(\mathrm{mod}p)\end{array}$$
两边同乘$inv(ir)$整理后可得
$$\begin{array}{rl}(p-k)i\times inv(ir)& \equiv r\times inv(ir)\\ (p-k)i\times inv(i)inv(r)& \equiv r\times inv(r)inv(i)\\ inv(i)\equiv (p-k)inv(r)& \iff \\ inv(i)& \equiv (p-\lfloor p/i\rfloor )inv(r)\end{array}$$
于是代码

#include <cstdio>
#include <vector>long long inv[3000001];int main()
{long long  n;long long p;scanf("%lld%lld", &n, &p);inv[1] = 1;for ( int i = 1;i <= n; i++) {if ( i != 1) {inv[i] = (p - p / i) * inv[ p % i] % p;}printf("%lld\n", inv[i]);}return 0;
}

5. 参考

czc1999
let_life_stop