题解：P10404 「XSOI-R1」原神数

Alastair · 2024-05-09 17:42:40 · 题解

首先可以如果只考虑数字不重复，数字数量不超过 5 \times 10^6。

那么我们只需要考虑数字不重复时的质数，由于直接 O(\sqrt N) 的质数判断会超时，使用 Miller-Rabin 素性测试，然后记录下合法的原神数，对每次询问二分输出答案。