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
| #include<iostream>
#include<cstdio>
using namespace std;
typedef long long LL;
int num,P,gcd;
LL A[3000005];
void exgcd(int a,int b,int &x,int &y) {
if(b==0) {gcd=a;x=1;y=0;}
else {exgcd(b,a%b,y,x);y-=x*(a/b);}
}
LL fast_pow(LL B, LL x) {
LL tmp=1;
while (x>0) {
if (x&1) tmp=tmp*B%P;
B=B*B%P;
x>>=1;
}
return tmp;
}
int main() {
cin >> num >> P;
int x,y;
exgcd(num,P,x,y);
printf("%d\n",(x%P+P)%P);
printf("%d\n",fast_pow(num,P-2));
A[1]=1;printf("%d\n",A[1]);
for(int i=2;i<=num;i++) {
A[i]=(P-(P/i))*A[P%i]%P;
printf("%d\n",A[i]);
}
return 0;
}
|