题解：CF2041F Segmentation Folds
沉石鱼惊旋
·
·
题解
F. Segmentation Folds
给定 [l,r]，你需要选择以下操作任一执行：
-
选择一个最大的 x(l\lt x\leq r) 满足 l+x 是质数，[l,r]\to [\frac{1}{2}(l+x),r]。
-
选择一个最小的 x(l\leq x\lt r) 满足 r+x 是质数，[l,r]\to [l,\frac{1}{2}(r+x)]。
如果这个区间 [l,r] 无法操作，则称这个区间为一个结束状态。否则继续递归。
问所有结束状态中，长度最小的有多少个。答案对 998244353 取模。
多测，1\leq t\leq 10。
---
为了规避浮点问题，我们把所有区间的 $l,r$ 都乘上 $2$。
我们首先要把 $[2l,2r]$ 之间的素数都筛出来。我们先预处理到 $\sqrt{2r}$ 的所有质数，然后把这些质数在 $[2l,2r]$ 内的倍数筛出来。具体参见 [P1835 素数密度](https://www.luogu.com.cn/problem/P1835)。
然后大力搜索即可。
搜索的时候可以通过二分找到第一个和最后一个合法的 $x$。但是这样复杂度多带一个 $\log$。我们把二分的内容拎出去，在预处理完质数之后，枚举所有的情况找到上一个下一个质数。
搜索的结束状态一定是两个相邻的质数。只有 $\mathcal O(\frac{n}{\log n})$ 个。而每个状态只有 $\mathcal O(\log n)$ 个前驱状态，所以直接搜索甚至不带记忆化的复杂度是 $\mathcal O(n)$ 的。
总复杂度瓶颈在筛质数的 $\mathcal O(n\log \log n)$。
代码写的有点丑了，丑在了：
>我们把二分的内容拎出去，在预处理完质数之后，枚举所有的情况找到上一个下一个质数。
这一部分。写的是二分，如果写双指针最后复杂度就是 $\mathcal O(n\log \log n)$。这份代码是 $\mathcal O(n\log n)$ 的。
<https://codeforces.com/contest/2041/submission/294604119>