题目大意：给定正整数$n$，求出$n$的所有原根。多组数据。
题解
模板题，但这个题卡时间卡的比较紧，所以要先用线性筛筛出质数，顺便预处理出每一个范围内的数的欧拉函数。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
110
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int p, pri[105], cnt, ans[1000005], len;
int phi[1000005], prime[500005], tot = 0;
bool vis[1000005] = {0}, ok[1000005] = {0};
void getPhi(int N){
phi[1] = 1;
for(int i = 2; i <= N; ++i){
if(!vis[i]){
prime[++tot] = i, phi[i] = i - 1;
if(i & 1){
for(int j = i; ; j *= i){
ok[j] = true;
if(j + j <= N) ok[j + j] = true;
if(1ll * j * i > N) break;
}
}
}
for(int j = 1; j <= tot; ++j){
ll t = 1ll * i * prime[j];
if(t > N) break;
vis[t] = true, phi[t] = phi[i] * (prime[j] - 1);
if(i % prime[j] == 0){
phi[t] += phi[i];
break;
}
}
}
}
int poww(int a, int b, int M){
int res = 1;
while(b){
if(b & 1) res = (1ll * res * a) % M;
a = (1ll * a * a) % M, b >>= 1;
}
return res;
}
void getFac(int x){
cnt = 0;
int t = x;
for(int i = 1; i <= 168; ++i){
if(t % prime[i] == 0){
do{
t /= prime[i];
}while(t % prime[i] == 0);
pri[++cnt] = prime[i];
}
if(t == 1) break;
}
if(t != 1) pri[++cnt] = t;
}
bool judge_pr(int x){
if(poww(x, phi[p], p) != 1) return false;
for(int i = 1; i <= cnt; ++i)
if(poww(x, phi[p] / pri[i], p) == 1)
return false;
return true;
}
int get_pr(int p){
for(int i = 2; i <= p; ++i)
if(judge_pr(i)) return i;
return -1;
}
int gcd(int a, int b){
return (!b) ? a: gcd(b, a % b);
}
void solve(){
if(p == 1 || p == 2) {
printf("1\n");
return ;
}
if(p == 4) {
printf("3\n");
return ;
}
if(!ok[p]){
printf("-1\n");
return ;
}
getFac(phi[p]);
int res = get_pr(p);
len = 0, ans[++len] = res;
for(int i = 2, j = 1ll * res * res % p; i < phi[p]; ++i, j = 1ll * j * res % p){
if(gcd(i, phi[p]) == 1) ans[++len] = j;
}
sort(ans + 1, ans + len + 1);
for(int i = 1; i < len; ++i)
printf("%d ", ans[i]);
printf("%d\n", ans[len]);
}
int main(){
getPhi(1000000);
while(~scanf("%d", &p)){
solve();
}
return 0;
}