P3811 【模板】乘法逆元

---

P3811 【模板】乘法逆元

---

时间限制 500ms
内存限制 125.00MB

题目背景

这是一道模板题

题目描述

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

输入格式

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

输出格式

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

输入输出样例

输入 #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\)为质数。

推荐zjp_shadow的乘法逆元小结

递推代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3e6+5;
long long n,p,inv[N];
int main(){
	scanf("%lld %lld",&n,&p);
	inv[1]=1; puts("1");
	for(int i=2;i<=n;++i){
		inv[i]=(p-p/i)*inv[p%i]%p;
		printf("%lld\n",inv[i]);
	}
	return 0;
}

求某数的乘法逆元

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define int long long
int n,p;
inline int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=res*a%p;
		a=a*a%p;
		b>>=1;
	}
	return res%p;
}
signed main(){
	scanf("%lld %lld",&n,&p);
	printf("%lld\n",qpow(n,p-2));
	return 0;
}