题解：CF2158F1 Distinct GCDs (Easy Version)

· · 题解

CF2158F1 Distinct GCDs (Easy Version)

首先把所有 \left(x,y\right) 满足 1\le x< y\le n 的数对拿出来，考虑每个 \gcd\left(a_x,a_y\right) 都不同的情况。一个很显然的构造是找到一个常数 c，构造 c+1 个数，其中第 i 个数为 2^{i-1}\times 3^{c+1-i}。这样 \gcd\left(a_x,a_y\right)=2^{x-1}\times 3^{c+1-y}，显然不会出现重复。

考虑最终答案序列 ans。由于现在 \gcd(a_x,a_y) 不会出现重复，那么只需要满足不存在 i,j 使得 \left\{ans_i,ans_{i+1}\right\} 和 \left\{ans_j,ans_{j+1}\right\} 这两个集合相同即可。那么我们将 ans_{i-1} 与 ans_i 之间连一条边，其等价于在一个大小为 c+1 完全图上找一条长度为 n 的路径（不一定是简单路径）满足每条边只经过了一次且途经的不同点的数量最小。

如果没有最小化点数量的要求那么直接跑欧拉路即可。因此考虑枚举答案序列中不同的点的数量，再建完全图跑欧拉路。

这时候还有个问题，设完全图大小为 k，如果 k 为偶数那么这张图就不存在欧拉回路。一个很简单的想法是把所有为偶数的 i 将 \left(i,i+1\right) 这条边给删掉，但可以发现这样不是最优的。因为我们不一定要欧拉回路，欧拉路径也可以，所以将 \left(1,2\right) 这条边要保留下来。

分析一下现在能构造出来的序列的长度。对于大小为 k 的完全图，当 k 为奇数时可构造的路径长度为 \frac{k(k-1)}{2}，当 k 为偶数时是 \frac{k(k-1)}{2}-\frac{k}{2}+1。此时最多构造出来的长度是 666，还是差了点。

可以发现实际上每个数可以和其自己连一条边。所以我们对于答案序列中的每个数将其第一次出现的位置后面再塞一个他自己。这样对于大小为 k 的完全图可以额外增加 k 个数进来。此时最长长度为 703，完全胜利！

code