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)\) 递推了。

代码

#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;
}