【XR-3】Unknown Mother-Goose
由于 \(|S|\) 并不大，如果每个元素都足够大的话，我们完全可以直接用 \(S\) 里的每一个数都暴力标一遍 \(1\sim n\) 的所有数，复杂度是 \(\mathcal{O}(|S|\dfrac{n}{w})\) ，其中 \(w\) 是 \(|S|\) 中最小的数。
但是如果最小的数不够大，那这个复杂度就不好看了。为了使问题简单化，我们不妨单独考虑较小的数，较大的数则直接暴力标记。
假设 \(d\) 是区分大小数的基准，大于等于 \(d\) 的数暴力标，否则单独考虑。对于小于 \(d\) 的数 \(w\) ，我们希望它暴力的复杂度能从 \(\mathcal{O}(\dfrac{n}{w})\) 降到 \(\mathcal{O}(\dfrac{n}{d})\) 。仔细想一下，暴力标的过程类似于分块，相当于我们每 \(d\) 个数分成一个块，每个数对应不同的余数，可以发现，在按照 \(d\) 分块的基础上暴力标 \(w\) ，每个块内会有某些位置的数被标记，而可能出现的位置种数一定会在经过第 \(w\) 个块之后开始重复。也就是说，前 \(w\) 个块的标记情况足以反映出 \(1\sim n\) 的标记情况，而这 \(d\) 个数最多只需要统计前 \(d\) 个块的情况。
于是，我们只需要按照 \(d\) 进行分块，对于 \(1\sim d\) 每个数都暴力统计前 \(d\) 个块内的标记情况，对于大于 \(d \times d\) 的数我们可以快速得知它的块与 \(1\sim d\) 的哪一个块的情况相同，从而可以在对 \(|S|\) 中大于 \(d\) 的数暴力标记同时直接查找它对于小于 \(d\) 的数的标记情况。
具体而言，对于小于 \(d\) 的数 \(w\) ，我们记录 \(\bmod{w}\) 分别等于 \(0, 1, 2\) 的数的情况。假设当前考虑的是等于 \(0\) 的情况，用一个长度为 \(d\) 的 \(01_k\) 串来表示某个块内被标记的数是在第 \(k\) 个位置，串的第 \(i\) 位为 \(1\) 则表明第 \(i\) 个块的第 \(k\) 个数\(\mod{w}=0\) .
根据我们的做法，\(d\) 取 \(64\) 会比较合适，这些 \(01\) 串则可以用一个 bitset<64>status[64][3] 来存储最后利用位运算来判断是否满足条件。