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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
| var n,m,t,t1,t2,tt,tt2,i,j:longint;
mo:int64;
b,d,g,mm:array[0..10001] of int64;
c:array[0..10001,0..4] of int64;
p:array[0..100001] of boolean;
function exgcd(x,y:longint;var tx,ty:longint):longint;
var t1:int64;
begin
if y=0 then begin
tx:=1;ty:=0;
exit(x);
end;
exgcd:=exgcd(y,x mod y,tx,ty);
t1:=tx;tx:=ty;ty:=t1-(x div y)*ty
end;
procedure qsort(x,y:longint);
var i,j,k:longint;
begin
i:=x;j:=y;
k:=g[(i+j) div 2];
while i<=j do begin
while g[i]<k do inc(i);
while g[j]>k do dec(j);
if i<=j then begin
g[0]:=g[i];g[i]:=g[j];g[j]:=g[0];
inc(i);dec(j);
end;
end;
if i<y then qsort(i,y);
if x<j then qsort(x,j);
end;
procedure sy;
var i:longint;
ans:int64;
begin
ans:=0;
for i:=1 to tt do begin
exgcd(mm[i],b[i],t1,t2);
ans:=(ans+((d[i]*t1) mod mo*mm[i]) mod mo+mo*10) mod mo;
end;
inc(tt2);
g[tt2]:=ans;
end;
procedure dfs(x:longint);
var i:longint;
begin
if x=tt+1 then begin
sy;
exit;
end;
for i:=1 to c[x,0] do begin
d[x]:=c[x,i];
dfs(x+1);
end;
end;
begin
readln(n);
mo:=n;
t:=trunc(sqrt(n));
tt:=0;
m:=n;
for i:=2 to t do
if not p[i] then begin
if m mod i=0 then begin
inc(tt);
t2:=i;
b[tt]:=1;
while m mod i=0 do begin
m:=m div i;
b[tt]:=b[tt]*t2;
end;
end;
j:=i;
while j<=t do begin
p[j]:=true;
j:=j+i;
end;
end;
if m<>1 then begin
inc(tt);
b[tt]:=m;
end;
for i:=1 to tt do begin
if b[i] mod 2=0 then begin
if b[i]=2 then begin
c[i,0]:=1;
c[i,1]:=1;
end else if b[i]=4 then begin
c[i,0]:=2;
c[i,1]:=1;
c[i,2]:=3;
end else begin
c[i,0]:=4;
c[i,1]:=1;
c[i,2]:=b[i] div 2-1;
c[i,3]:=b[i] div 2+1;
c[i,4]:=b[i]-1;
end;
end else begin
c[i,0]:=2;
c[i,1]:=1;
c[i,2]:=b[i]-1;
end;
end;
for i:=1 to tt do mm[i]:=n div b[i];
dfs(1);
qsort(1,tt2);
for i:=1 to tt2 do writeln(g[i]);
end.
|
