捏捏小圆脸 | 【题解】P12001 在小小的奶龙山里面挖呀挖呀挖

Starrykiller · 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)，可以通过。