反方向的钟 题解

· · 题解

其实样例特意凑了一下，在 n=3 的时候可以做到这种有误导性的最优构造。

部分分其实没有很好讲的，主要是引导往 n=2^k 时的构造上思考，从而引导出一般情况。这题其实很难出部分分，几乎是一道更适合无部分分赛制的题目。事实上本来也是投给了 CF，但那场鸽子太久倒闭了。

只考虑 n\ge3。由于 \gcd(x,y)\mid x，故 |S_x|\le d(x)\le2^{\Omega(x)}。若 |S_x|=2^{\Omega(x)}，则 \exists y\in S\backslash\{x\}，x\mid y，从而 \Omega(y)\ge\Omega(x)+1。因此 \max\limits_{x\in S}\{\Omega(x)\}\ge\log_2(|S_x|+1)=\log_2n。

由于 \max\limits_{x\in S}\{\Omega(x)\} 为整数，我们只考虑 n=2^k 的情况，此时试图给出 \max\limits_{x\in S}\{\Omega(x)\}=k 的构造。同时有一个简单的观察：在 S 的一个子集内，条件是不强于在 S 内的，因为条件 1 本质上是要求 S_x 中元素互不相同，这在满足条件的 S 的子集内是自然继承的。因此我们对于一般的 n 同样只需构造出 2^k\ge n 的最小的 2^k 时的一个 S，再取一个大小为 n 的子集即可。

对于构造，发现要使 d(x)\ge|S_x|=2^k-1，必须使 x 为 k 个不同质数的乘积。尝试一些情况后可以发现取两个大小为 k 的质数集 P_0,P_1，将 S 中元素编号为 0\sim2^k-1，第 m 个元素为其第 i 个二进制位对应下标的 P_j 中第 i 个质数之乘积即可满足条件 1,2。

具体地，举例 n=4：取 P_0=\{2,3\},P_1=\{5,7\}，则 S=\{2\times5,3\times5,2\times7,3\times7\}，容易验证其满足条件。

为了使 S 中元素尽可能小，我们直接取 P_0 中第 i 个元素为第 2i-1 小的质数，P_1 中第 i 个元素为第 2i 小的质数，发现在 n=4\times10^3 时，对 2^{12}=4096 时构造出的 S 排序后第 n 小的数不超过 3\times10^{17}。

事实上这个界相当紧，而且还是 O(n^2\log V) 的 checker 好写，简直是天作之合（嗯）。虽然人傻写的 checker 爆慢结果开了 2.5s 的时间限制。