【模板】乘法逆元

题目背景

这是一道模板题

题目描述

给定 \(n,p\) 求 \(1\sim n\) 中所有整数在模 \(p\) 意义下的乘法逆元。

这里 \(a\) 模 \(p\) 的乘法逆元定义为 \(ax\equiv1\pmod p\) 的解。

输入格式

一行两个正整数 \(n,p\)。

输出格式

输出 \(n\) 行，第 \(i\) 行表示 \(i\) 在模 \(p\) 下的乘法逆元。

样例 #1

样例输入 #1

10 13

样例输出 #1

1
7
9
10
8
11
2
5
3
4

提示

\(1 \leq n \leq 3 \times 10 ^ 6, n < p < 20000528\)

输入保证 \(p\) 为质数。

解题思路：

由于\(n\)的取值很大所以要用线性的求法得出逆元：
首先，\(i=1\)的逆是\(1\)。下面是求\(i \gt 1\)时的逆，用递推法。
设\(\frac{p}{i} \, =k\),余数是\(r\),即\(k \bullet i +r \equiv 0 (mod \; p)\);
在两边乘\(i^{-1} \bullet r^{-1}\),得到\(k \bullet r^{-1} + i^{-1} \equiv 0(mod \; p)\);
移项得到\(i^{-1} \equiv -k \bullet r^{-1} (mod \; p)\),即\(i^{-1} \equiv -\frac{p}{i} \bullet r^{-1}(mod \; p)\),\(i^{-1} \equiv (p-\frac{p}{i}) \bullet r^{-1} (mod \; p)\)。

Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=3e6+5;
int n,p,inv[maxn];
inline void inverse(int n,int p) {
	inv[1]=1;
	for(int i=2;i<=n;i++) 
		inv[i]=(p-p/i)*inv[p%i]%p;
}
signed main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>p;
	inverse(n,p);
	for(int i=1;i<=n;i++)
		cout<<inv[i]<<'\n';
	return 0;
}