P17142

· · 题解

关键观察：若我们一直 w\in S，直接 query S 即可确定答案，因为 \sum \gcd 的变化量就是 w。

做法的核心思想是：前三次询问尽量缩小答案候选集合 S，第四次直接问 S。

先随 n=100 个长为 len 的序列，预处理其可以划分出的等价类（同一个等价类内的数无法通过该询问序列区分）。每次找到可以最好的区分 S 内数的序列（即划分出的最大等价类大小最小）。复杂度 \mathcal{O}(Tnm)，进行一些调参可以获得 72 分。提交记录。

没有必要在最开始随序列。我们要做的是对于固定的 $S$ 尽可能地找到一个可以最好地区分其的序列，稍微构造一下，我们有几种序列方案： - A：纯随。 - B：放一些多因数的数。 - C：保持相邻两个数差为 $B+r$，其中 $B=\frac{m}{len}$ 为常数，$r\le \mathcal{O}(1)$ 对于每个数随机取一个，这样子使得相邻两个数 $\gcd>1$ 概率大大提升（但也控制在较小的范围内，使得区分度大大提升）。 - D：直接从 $S$ 里掏一些数。 - E：放一个连续的素数区间。 按比例随机，可以非常好地进行区分（尤其是对于素数，这是直接随机最难以区分的东西）。进行精细的调参后可以获得 $\operatorname{totalsize}=26$ 的解（远优于题目限制/标算的 $35$）！以下代码由 AI 生成：[提交记录](https://qoj.ac/submission/2674453)。