前言
题目传送门 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)\) 递推了。
代码
#include<iostream>
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define MIKU 0
using namespace std;int n, p;
int inv[3000005] = {0, 1};signed main() {fastio;cin>>n>>p;cout<<1<<'\n';for(int i=2; i<=n; i++) {inv[i] = (p - p / i) * inv[p % i] % p;cout<<inv[i]<<'\n';}return MIKU;
}