### Primitive Roots LeeRinji

1. 有原根的数只有$2,4,p^n,2p^n$（$p$为质数，$n$为正整数）。
2. 一个数的最小原根的大小是$O(n^{\frac{1}{4}})$的。
3. 如果$g$为$n$的原根，则$g^d$为$n$的原根的充要条件是$\gcd (d,\phi (n))=1$；
4. 如果$n$有原根，它的原根个数为$\phi (\phi (n))$。

#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");
}
}