【-31】P3811 【模板】乘法逆元

题目描述

给定 $n,p$ 求$1$~$n$中所有整数在模 $p$意义下的乘法逆元。

输入输出格式

输入格式:

一行 $n,p$

输出格式:

$n$ 行,第 $i$ 行表示 $i$ 在模 $p$ 意义下的逆元。

输入输出样例

输入样例#1:

1
10 13

输出样例#1:

1
2
3
4
5
6
7
8
9
10
1
7
9
10
8
11
2
5
3
4

说明

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

输入保证 $p$ 为质数。

题解

看了这篇

http://blog.csdn.net/outer_form/article/details/51509360

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
int P[10],l;
void write(int x)
{
if (!x) putchar(48);
else
{
l=0;
while(x) P[++l]=x%10,x=x/10;
while(l) putchar(48+P[l--]);
}
putchar(10);
}
int n,p;
int f[20000558];
int main()
{
n=read();
p=read();
f[1]=1;
printf("%d\n",1);
for (int i=2;i<=n;i++)
{
f[i]=(long long)(p-p/i)*(long long)f[p%i]%p;
write(f[i]);
}
return 0;
}