Primitive Roots

题目链接

把一个数的所有比它小的原根求出来。这里有一篇博客(Fenghr)说的挺好,先转过来:

所谓原根就是说,对于一个数$n$,$x^k\equiv 1\pmod n$的最小正整数 k 是$\phi (n)$,即 n 的欧拉函数,那么就称$x$是$n$的原根。原根有很多美丽的性质。比如说:

  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))$。

那么来看一下这道题:

首先根据性质 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}})$的。

找到之后枚举次方就可以了,因为是充分条件。

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