原根 学习笔记

数论中的一个小概念，也是 NTT 的基础。

阶

若 $\gcd(a,m) = 1$，使 $a^l \equiv 1 \pmod m$ 成立的最小正整数 $l$，称为 $a$ 关于模 $m$ 的阶，记为 $\text{ord}_m a$。

若 $\text{ord}_m a = l$，则 $\text{ord}_m a^t = \frac{l}{\gcd(t,l)}$。

若 $\text{ord}_m a = l$，则 $a^n \equiv 1 \pmod m$ 当且仅当 $l|n$，特别地，$l | \varphi(m)$。

原根

若 $\text{ord}_mg = \varphi(m)$，则称 $g$ 是 $m$ 的一个原根。

判断是否有原根

若 $m$ 有原根，则 $m$ 一定是 $2,4,p^a,2p^a$ 的形式，这里的 $p$ 为奇质数，$a$ 为正整数。

求所有原根

设 $g$ 为 $m$ 的一个原根，则对于 $s \in [1,\varphi(m)]$ 且 $\gcd(s, \varphi(m)) = 1$，$g^s$ 为 $m$ 的全部原根。因此，若 $m$ 有原根，则 $m$ 有 $\varphi(\varphi(m))$ 个原根。

求一个原根

若 $g$ 是 $m$ 的原根，当且仅当 $\gcd(g,m) = 1$，且对于 $\varphi(m)$ 的任意一个质因子 $p$，都有 $g^{\frac{\varphi(m)}{p}} \not\equiv 1 \pmod m$。

【模板】P6091 【模板】原根

int m, d, phi, qhi;
vector<pi> p, q;

inline void div(int n, vector<pi> &p, int &phi) {
	p.clear(), phi = n;
	for (int i = 2; i * i <= n; i++)
		if (!(n % i)) {
			phi = 1ll * phi * (i - 1) / i;
			p.pb(mp(i, 0));
			while (!(n % i)) ++p.back().se, n /= i;
		}
	if (n > 1) phi = 1ll * phi * (n - 1) / n, p.pb(mp(n, 1));
}

inline bool pd(int m) {
	if (m & 1) return p.size() == 1u;
	if (m == 2 || m == 4) return 1;
	return p.size() == 2u && p[0] == mp(2, 1);
}

inline int ksm(int a, int b, int m) {
	int c = 1 % m;
	while (b) {
		if (b & 1) c = 1ll * c * a % m;
		a = 1ll * a * a % m, b >>= 1;
	}
	return c;
}

inline bool chk(int g) {
	if (__gcd(g, m) > 1) return 0;
	for (pi o : q)
		if (ksm(g, phi / o.fi, m) == 1) return 0;
	return 1;
}

inline void solve() {
	rd(m), rd(d);
	div(m, p, phi);
	if (!pd(m)) return prints("0\n");
	div(phi, q, qhi);
	int g = 1;
	while (!chk(g)) ++g;
	print(qhi);
	vi ans;
	for (int i = 1, G = g; i <= phi; i++, G = 1ll * G * g % m) {
		if (__gcd(i, phi) > 1) continue;
		ans.pb(G);
	}
	sort(ans.begin(), ans.end());
	for (int i = 1; i <= qhi; i++)
		if (!(i % d)) print(ans[i-1], ' ');
	prints("");
}

int main() {
	int T;
	rd(T);
	while (T--) solve();
	return 0;
}

参考资料

• OI Wiki 原根