自动搬运

查看原文

来自洛谷，原作者为

	Starrykiller 祈祷着今后的你的人生，永远都有幸福的「魔法」相伴。

搬运于2025-08-24 23:12:01，当前版本为作者最后更新于2025-03-29 18:29:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

无脑做法。

不大于 $V=10^5$ 的素数只有 $\pi(V)\sim 10^4$ 个。

考虑用一个 bitset 压下来，然后做静态树上链查询即可。我使用了点分治，时间复杂度 $\Theta((n+q)\log n\sqrt{\pi(V)}/w)=\Theta((n+q)\log n\sqrt{V/\log V}/w)$，可以通过。