【题解】CF1406E Deleting Numbers

CF1406E Deleting Numbers

交互题。
给定 $n$，则一开始有集合 $S=\{x|x\le n,x\in \mathbb{N}^+\}$，其中有一个特殊值 $x$，你需要通过以下操作找到他。
$\texttt{A}\ a$：询问集合 $S$ 中 $a$ 的倍数个数 $(1\le a \le n)$。
$\texttt{B}\ a$：先询问集合 $S$ 中 $a$ 的倍数个数，然后删去所有还在 $S$ 中的 $a$ 的倍数，而 $x$ 不会被删去 $(2\le a \le n)$。
$\texttt{C}\ a$：回答 $x=a$。
$\texttt{A,B,C}$ 操作的个数和不能超过 $10000$。
$1 \le x \le n\le 10^5$。

$\texttt{Solution}$

以下设 $pr(n)$ 为 $n$ 以内的质数个数。

首先有最 $\texttt{naive}$ 的做法，筛出 $10^5$ 之内所有质数，然后每个做一遍 $\texttt{B}$。则现在剩下的只有 $x$ 这一个数字，对每一个质数 $p$，每次对 $p^x$ 做 $\texttt{A}$ 即可判断 $x$ 中每个质数的个数。这样询问大概是 $\mathcal{O}(2\times pr(n)+\log x)$ 的，而 $pr(10^5)=9592$，以上询问个数显然大于 $10000$。

众所周知，一个数 $x$ 最多有一个 $\sqrt{x}$ 以上的质因子。所以，我们对 $\sqrt{n}$ ~ $n$ 之内的质数都做一遍询问太浪费了。考虑如何优化，首先对于 $\sqrt{n}$ 以下的质数，我们用上面的算法，可以求出 $x$ 所有 $\sqrt{n}$ 以下的质因子的乘积，询问个数 $\mathcal{O}(2\times pr(\sqrt{n})+\log x)$，而 $pr(\sqrt{10^5})=65$，因此大概需要 $200$ 次询问左右。

然后，$S$ 中就只剩下 $x$ 和所有 $\sqrt{n}$ 以上的质数了。考虑如何能够用更少的询问找出这个质因数。注意到 $\texttt{A}$ 是可以询问 $1$ 的，也就是问 $|S|$，所以考虑充分利用这个条件。令 $m=pr(n)-pr(\sqrt{n})$，那不难想到按照 $\sqrt{m}$ 为块长对剩下的质数进行分块处理。

我们每 $\sqrt{m}$ 个质数一起进行 $\texttt{B}$ 操作，将这些 $\texttt{B}$ 给出的回答存到计数器 $cnt$ 中。

如果 $x$ 的质因子不在这 $\sqrt{m}$ 个质数中，那么在操作这个块之前、之后询问 $\texttt{A}\ 1$，其差值应该正好是 $cnt$，因为他们都会被删掉。

那如果在呢？那么他们的差值一定比 $cnt$ 小 $1$。因为 $cnt$ 中记上了 $x$，但是 $x$ 不会被删掉，所以一定只删去了 $cnt-1$ 个数字！这样就可以很快速地求 $x$ 在哪个块中。

那如何确定是这个块中的谁呢？再对块中每个质数做一遍 $\texttt{A}$ 即可。由于我们确定这样的质数最多一个，所以找到之后直接结束循环。说不定可以减少很多询问

算一下询问数应该是 $\mathcal{O}(2\times pr(\sqrt{n})+\log x+m+\sqrt{m})$，其中 $m=pr(n)-pr(\sqrt{n})$，好像有 $9700+$？懒得算。挺卡的，实现需要精细一点。

时间复杂度 $\mathcal{O}(pr(n))$ 左右吧。