原来一般的四度图也没法快速构造哈密顿回路 QwQ
# 题面
给定质数 \(P\) 和正整数 \(a,b\)，构造一个长为 \(P\) 的数列 \(G=(g_1,g_2,\dots,g_P)\)，满足：
\(g_1=g_P=1\)；
\((g_1, g_2,\dots,g_{P-1})\) 是 \(1\sim P-1\) 的排列；
\(\forall 1\le i\le P-1\)，\(g_i\) 和 \(g_{i+1}\) 满足下述关系之一：
\(g_i=ag_{i+1}\)；
\(ag_i=g_{i+1}\)；
\(g_i=bg_{i+1}\)；
\(bg_i=g_{i+1}\)。
判断是否有解，若有解，给出任意一组。
数据规模：\(P\le10^5,1\le a,b\lt P\)。
# 解析
转化为图论问题，若 \(i, j\) 满足题面所述的性质，则在 \(i, j\) 之间连边。需要找到一条哈密顿回路（经过所有点恰好一次）。显然这个图的每个点度数都是 \(4\)，虽然没什么用。
不额外说明的话，以下的计算均是在模 \(P\) 意义下的。
\(P\) 是质数，意味着 \(a,b\) 都有逆元，进一步意味着「将 \(i\) 与 \(a\cdot i\) 连边」会得到若干个大小为 \(\mathrm{ord}_a\) 的环。
结论
令 $n=\mathrm{ord}_a$，数集 $H=\{a^i\mid i\in \mathbb Z\}$，$m$ 为满足 $b^{m_0}\in H$ 且 $m_0\ge 1$ 的最小 $m_0$。
则问题有解当且仅当 $nm = P - 1$；若 $nm = P - 1$，则 $\forall 1\le x\le P - 1$，存在唯一的 $i \in [0, n), j \in [0, m)$，使得 $x = a ^ i b ^ j$。
根据定义，下述结论是显然成立的：
$$
\{a ^ i b ^ j \mid i, j \in \mathbb Z\}=\{a ^ i b ^ j \mid i \in [0, n), j \in [0, m), i,j \in \mathbb Z\}
$$
原问题有解的必要条件是
\(\forall 1\le x\le P - 1\)，\(\exists i, j \in \mathbb Z, x = a ^ i b ^ j\)；
即
\[\begin{aligned}
&\{x\mid 1\le x\le P - 1\}=\{a ^ i b ^ j \mid i, j \in \mathbb Z\}=\{a ^ i b ^ j \mid i \in [0, n), j \in [0, m)\}\\
\Rightarrow&\Big|\{x\mid 1\le x\le P - 1\}\Big| = \Big|\{a ^ i b ^ j \mid i \in [0, n), j \in [0, m)\}\Big|\\
\Rightarrow&P-1=nm
\end{aligned}
\]
必要性得证。下证上述结论中的第二条，即可构造出一组解，从而证明充分性。
下述 \(a\) 的指数上的运算在模 \(n\) 意义下，\(b\) 的指数上同理在模 \(m\) 意义下。
每个数都能表示成 \(a^ib^j\) 的形式，存在性显然；只需证明唯一性。假设存在一个 \(x\in[0,P)\)，使得 \(x=a^ib^j=a^pb^q\)（\(a,p\in[0,n)\)，\(b,q\in[0, m)\)），则
\[a^{i-p}\equiv b^{q - j}
\]
若 \(j\neq q\)，则 \(0\lt q-j\lt m\)，根据「\(m\) 是最小的满足 \(b^m\in H\) 的正整数」，\(b^{q-j}\neq a^{i-p}\)。矛盾，则 \(j=q\)。
\[a ^ {i - p} \equiv 1
\]
若 \(i\neq p\)，则 \(0\lt i - p\lt n\)，根据「\(n\) 是最小的满足 \(a^n=1\) 的正整数」，\(a ^ {i - p} \neq 1\)。矛盾，则 \(i = p\)。
所以 \(i, j\) 具有唯一性。
于是我们可以用 \(a ^ i b ^ j\)（\(i \in [0, n), j \in [0, m)\)）唯一表示 \(1 \sim P - 1\) 的数，可以按照下述方式构造 \(n \times m\) 的表格：
第 \(i\) 行第 \(j\) 列放置数 \(a ^ {i - 1} b ^ {j - 1}\)。
\(1 \sim P - 1\) 在表格上恰好出现了一次，且表格上相邻的两个数都有边相连 —— 所以这是一个网格图。
再分析，\(P - 1\) 是偶数，\(nm = P - 1\)，\(n, m\) 至少有一个是偶数。行和列至少有一个是偶数的网格图可以直接构造哈密顿回路，可以求解，也证明了结论的充分性。
# 源代码
/*Lucky_Glass*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#define con(typ) const typ &
const int N = 1e5 + 10;
int mod, va, vb, n, m, nans;
bool vis[N];
int ans[N], powa[N], powb[N];
inline int mul(con(int) a, con(int) b) {return int(1ll * a * b % mod);}
int main() {
scanf("%d%d%d", &mod, &va, &vb);
vis[1] = true;
n = m = 1;
for (int tmp = va; tmp != 1; ++n, tmp = mul(tmp, va))
vis[tmp] = true;
for (int tmp = vb; !vis[tmp]; tmp = mul(tmp, vb), ++m) ;
if ( mod - 1 != 1ll * n * m ) {printf("No\n"); return 0;}
if ( n & 1 ) std::swap(va, vb), std::swap(n, m);
powb[0] = powa[0] = 1;
for (int i = 1; i < n; ++i) powa[i] = mul(powa[i - 1], va);
for (int i = 1; i < m; ++i) powb[i] = mul(powb[i - 1], vb);
ans[++nans] = 1;
for (int i = 0, tmp = 1; i < n; ++i, tmp = mul(tmp, va))
if ( i & 1 )
for (int j = m - 1; j; --j)
ans[++nans] = mul(tmp, powb[j]);
else
for (int j = 1; j < m; ++j)
ans[++nans] = mul(tmp, powb[j]);
for (int i = n - 1; ~i; --i)
ans[++nans] = powa[i];
printf("Yes\n");
for (int i = 1; i <= nans; ++i) printf("%d%c", ans[i], i == nans ? '\n' : ' ');
return 0;
}
THE END
Thanks for reading!
满眼繁星占领我内心
撑起腐朽夜空
手点着微芒 想照亮那隐约角落
转瞬即逝 如烟火抱憾落幕
将我隐藏 成为星空崭新的孤岛
——《一封孤岛的信》 By 著小生 / 洛天依
> 一封孤岛的信 - Bilibili
