CF1981D Turtle and Multiplication 题解

来水一篇题解

十分简单的 $2400$。考虑到质数的因子数量相对较少，而且两个数 $a_1,a_2$ 若能表示为 $a_1=p_1p_2,a_2=p_3p_4$ 的形式（$\forall i\in[1,4],p_i\in\text{prime}$），则 $a_1=a_2$ 当且仅当 $\lbrace p_1,p_2\rbrace=\lbrace p_3,p_4\rbrace$。因此考虑二分选前 $m$ 个质数建图，对于任意两个质数都连一条边。然后就是问图上是否存在一个子边集使得这个子边集和点集合起来形成的新图存在欧拉路径，可以使用 Hierholzer Algorithm 求解，时间复杂度为 $O(n\log n)$。

太慢了，能不能优化？考虑更快速的解决合法性问题，即询问 $n$ 个点的完全无向图选取子边集得到的新图的欧拉路径最长的长度，设这个答案为 $F(n)$，那么可以分奇偶讨论，有：

• 若 $2\nmid n$，则此时每一个点的度数都为 $n-1$，有 $2\mid n-1$，每一个点的度数都为偶数，此时原图就存在欧拉路径。
• 若 $2\mid n$，则此时每一个点的度数都为奇数。考虑删掉 $n$ 号点和除了 $1$ 号点以外所有点的连边，此时 $1,n$ 两个点的度数为奇数，其余点度数全部为偶数。该新图存在欧拉路径。

计算上述两张图的边数就是 $F(n)$ 的值。

$F(n)$ 显然满足单调性，因此可以二分出最小需要选取前 $m$ 个质数，然后根据上面的方法来构造一张合法的图，跑欧拉路径即可。时间复杂度为 $O(n)$，可以通过。