CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
把一个数的所有比它小的原根求出来。这里有一篇博客（Fenghr）说的挺好，先转过来：
所谓原根就是说，对于一个数$n$，$x^k\equiv 1\pmod n$的最小正整数 k 是$\phi (n)$，即 n 的欧拉函数，那么就称$x$是$n$的原根。原根有很多美丽的性质。比如说：
- 有原根的数只有$2,4,p^n,2p^n$（$p$为质数，$n$为正整数）。
- 一个数的最小原根的大小是$O(n^{\frac{1}{4}})$的。
- 如果$g$为$n$的原根，则$g^d$为$n$的原根的充要条件是$\gcd (d,\phi (n))=1$；
- 如果$n$有原根，它的原根个数为$\phi (\phi (n))$。
那么来看一下这道题：
首先根据性质 1，我们可以通过预处理质数，把不存在的情况判掉。
然后根据性质 3，找到一个原根后枚举次方判$\gcd$就可以了。
怎么找到一个原根呢？按照性质 2 傻傻去跑在这种多组数据的题目里是肯定不行的。
那么有一个喜大普奔的结论来帮助我们：
因为$g^{\phi (n)}\equiv 1\pmod n$，而对于比 φ(n)小的数都不成立。
枚举$\phi (n)$的质因子 p，看$g^{\phi (n)/p}$在模意义下是否是 1。
是 1 的话$g$就不是原根。
证明起来有点麻烦，这里就不写了。
所以找原根大概是$O(n^{\frac{1}{8}})$的。
找到之后枚举次方就可以了，因为是充分条件。
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
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1000009;
struct EulerSieve
{
vector<int> p, m, phi;
EulerSieve(int N) : m(N, 0), phi(N, 0)
{
phi[1] = 1;
for (long long i = 2, k; i < N; ++i)
{
if (!m[i])
p.push_back(m[i] = i), phi[i] = i - 1;
for (int j = 0; j < p.size() && (k = i * p[j]) < N; ++j)
{
phi[k] = phi[i] * p[j];
if ((m[k] = p[j]) == m[i])
break;
phi[k] -= phi[i];
}
}
}
vector<int> fac(int nPhi)
{
vector<int> pt;
for (int i = 0; p[i] * p[i] <= nPhi; ++i)
if (nPhi % p[i] == 0)
for (pt.push_back(p[i]); nPhi % p[i] == 0;)
nPhi /= p[i];
if (nPhi > 1)
pt.push_back(nPhi);
return pt;
}
} e(N);
struct Mod
{
const ll M;
Mod(ll M) : M(M) {}
ll mul(ll a, ll b) const { return a * b % M; }
ll pow(ll a, ll b) const
{
ll r = 1;
for (a %= M; b; b >>= 1, a = mul(a, a))
if (b & 1)
r = mul(r, a);
return r;
}
};
struct PrimitiveRoots : vector<int>, Mod
{
PrimitiveRoots(int n, int nPhi) : Mod(n)
{
if (!check(n))
return;
vector<int> pt(e.fac(nPhi));
for (int i = 2, flag; i <= n; ++i)
if (pow(i, nPhi) == 1)
{
for (int j = flag = 0; !flag && j < pt.size(); ++j)
if (pow(i, nPhi / pt[j]) == 1)
flag = 1;
if (!flag)
{
for (int j = 1, k = i; j < nPhi; ++j, k = mul(k, i))
if (__gcd(j, nPhi) == 1)
push_back(k);
break;
}
}
}
bool check(int x) //模m有原根的充要条件是m=2,4,p^n,2(p^n),(p为奇质数，n为任意数）
{
if (x < 5)
return push_back(x - 1), 0;
if (x % 2 == 0)
x >>= 1;
if (x % 2 == 0)
return 0;
for (int i = 1; e.p[i] * e.p[i] <= x; ++i)
if (x % e.p[i] == 0)
{
while (x % e.p[i] == 0)
x /= e.p[i];
return x == 1;
}
return 1;
}
};
int main()
{
for (int n; ~scanf("%d", &n);)
{
PrimitiveRoots ans(n, e.phi[n]);
sort(ans.begin(), ans.end());
for (int i = 0; i < ans.size(); ++i)
printf("%d%c", ans[i], i + 1 == ans.size() ? '\n' : ' ');
if (ans.empty())
printf("-1\n");
}
}