题意简述
交互题，给定集合 \(S=\{1,2,\cdots,n\}\) 和一个隐藏的数 \(m\)，你需要使用不超过 \(10^4\) 次操作猜出 \(m\)，操作类型如下：
A x，查询在 \(S\) 中是 \(x\) 的倍数的数的个数。B x，查询在 \(S\) 中是 \(x\) 的倍数的数的个数，并把这些数删去，但是 \(m\) 不会被删去。C x，表示你猜的 \(m=x\)。
\(1\le m\le n\le 10^5\)。
分析
给出一个常数：\(p(10^5)=9592，r(10^5)\approx9700\)，\(p(n)\) 指的是 \([1,n]\) 的质数个数，\(r(n)\) 指的是 \([1,n]\) 的质数。
考虑到每个 \(m\) 都可以写成唯一分解的形式 \(\prod_i p_i^{c_i}\)，考虑枚举每一个 \(p_i\)，使用一次 B 操作删去 \(p_i\) 的所有倍数，然后查询此时 \(p_i\) 倍数个数。若为 \(1\)，那么 \(p_i\) 是 \(m\) 的其中一个质因子，暴力枚举每一个 \(p_i^k\) 使用 A 操作就能得到 \(m\) 在这个质因数下的具体指数。
但这样的询问次数是 \(p(n)+r(n)\approx19200>10^4\)，不能通过。
考虑优化，一个很经典的套路是对质因子根号分治，设阈值 \(B=\sqrt n\)，\(\le B\) 的质因子可以向之前那样暴力计算，而质数幂的数量大概在 \(\dfrac{B}{\ln B}\times \log_{p} n=O(B)\) 量级，次数较小，可以承受。
而 \(m\) 至多有一个 \(>B\) 的质因子，若 \(m\) 不为 \(1\) 或者 \(>B\) 的质数，那么我们只需要对每个质因子使用 A 操作，若 \(m\) 包含某个质因子，那么在对这个质因子使用 A 操作返回的答案是 \(2\)，那么只需要 \(p(n)\) 次操作就可以求出答案。
但如果 \(m\) 为 \(1\) 或者 \(>B\) 的质数，无论对那个质因子操作返回的答案都是 \(1\)，这种情况下我们只能使用暴力方案求解，次数还是爆炸。
发现对每个质因子都使用 A 操作 check 太浪费了，考虑把多个质因子批量删除之后一起使用 A 操作 check。对质因子分块，设块长 \(C=100\)，考虑逐块查询，将块内质因子用 B 操作删掉后查询 A 1，若返回的答案不为 剩余的质因子数+1，那么 \(m\) 落在这个块内，暴力 check 即可。次数为 \(B+p(n)-p(B)+C+\frac{p(n)}{C}\le 10^4\)，可以通过。