Luogu P3811 【模板】模意义下的乘法逆元 题解

前言

题目传送门 Luogu P3811 【模板】模意义下的乘法逆元
题意

求 \(1\sim n\) 中所有数在 \(\bmod\ p\) 意义下的乘法逆元。
思路

对于这种求一连串数的逆元的情况，一般的算法都会 \(\texttt{TLE}\) 。这时候，就需要一种 \(O(n)\) 的算法。也就是递推大人。
（以下记一个数 \(a\) 的逆元是 \(a^{-1}\)）
首先我们知道，\(1\) 的逆元 \(1^{-1}\) 是 \(1\) 。
然后我们设 \(p=ik+r\) ，也就是说，\(k\) 是 \(p\div i\) 的商，而 \(r\) 是余数。所以我们有如下同余式：

\[ki+r\equiv 0\ (\ \bmod\ p\ )\]
接下来，在同余式两边同乘 \(i^{-1}\cdot r^{-1}\) ，得到如下同余式：

\[kr^{-1}+i^{-1}\equiv 0\ (\ \bmod\ p\ )\]
移项，我们得到如下同余式：

\[i^{-1}\equiv -kr^{-1}\ (\ \bmod\ p\ )\]
即

\[i^{-1}\equiv -\left\lfloor \frac{p}{i} \right\rfloor r^{-1}\ (\ \bmod\ p\ )\]
由于负数取模会出现向零取整的问题，我们进行一点恒等变换，原式可化为：

\[i^{-1}\equiv (p-\left\lfloor \frac{p}{i} \right\rfloor)\cdot r^{-1}\ (\ \bmod\ p\ )\]
然后就可以 \(O(n)\) 递推了。
代码

[code]#include#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);#define int long long#define MIKU 0using namespace std;int n, p;int inv[3000005] = {0, 1};signed main() {        fastio;        cin>>n>>p;        cout