题解 P3811 【【模板】乘法逆元】
Ireliaღ
2019-07-24 13:07:34
## 这是一种不一样的线性逆元递推求法
~~其实也可以线性求出来任意一坨相乘得到的数的逆元~~
### 思路
根据逆元的意义，我们容易知道，如果我们知道$(xy)^{-1}(mod p)$，那么我们乘以$y$，就可以$O(1)$得到$x^{-1} (modp)$。
这样，$x$的逆元，可以利用$(x!)^{-1} \times (x - 1)!$这个式子求出来。所以，我们可以先递推出$n!$，然后用扩欧或者快速幂求出$(n!)^{-1}(modp)$，就可以反过来递推出$1$到$n$的所有逆元
### 代码
`cout`会超时，因为取消流同步和绑定只能加速`cin`
```cpp
// luogu-judger-enable-o2
#include <iostream>
using namespace std;
const int MAXN = 3e6 + 5;
int fac[MAXN], inv[MAXN], n, p;
int Exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int ret = Exgcd(b, a % b, y, x);
y -= 1LL * a / b * x;
return ret;
}
void GetInv(int x, int finv, int mod) {
if (x == 0) return;
int ninv = 1LL * finv * fac[x - 1] % mod;
GetInv(x - 1, 1LL * finv * x % mod, mod);
//cout << ninv << endl;
printf("%d\n", ninv);
}
int main() {
//ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> p;
fac[0] = 1;
for (int i = 1; i <= n; i++) fac[i] = 1LL * fac[i - 1] * i % p;
int x, y;
Exgcd(fac[n], p, x, y);
GetInv(n, (x + p) % p, p);
return 0;
}
```