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))$ 左右吧