CF1981D Turtle and Multiplication

· · 个人记录

全用质数是可以的。这样，我们考虑将所用的质数作为点，将所有点之间直接连边，表示这两个点可以相邻。任意一条边不能走一次以上。这就是一个欧拉回路问题。

我们考虑需要取多少个点。如果有 m 个点，那么每个点都和 m - 1 个点有边，同时有自环。那么是 m(m-1) / 2 + m 条边，也就是用 m 条边能构造出的最长的路径长度。

但是考虑当 2\mid m 时是不存在欧拉回路的。也就是，我们没法把这些边全都用上。所以我们把用不掉的删掉。删除一条边，最好能减少两个奇点，所以至少删掉 m/2 - 1 条边。这样能保证这张图存在一条欧拉路径。不妨把偶数到奇数的边删掉。