由于题目被修改，这篇题解已经做不了这个题了。

但是这篇题解介绍的东西还是有一定意义的，有兴趣的同学仍然可以阅读一下。

题目链接：https://www.luogu.com.cn/problem/P3383。

前言

首先说一下，这个科技是我在 Min_25 的博客里看见的，那篇博客是 2017 年的了，去翻了下提交记录发现论文哥也用了这个科技，所以也并不是什么新东西。有兴趣的也可以去阅读一下那篇博客。

然后，虽然这个题是线性筛素数，但是这篇题解并不是讲筛法的，而是一些奇技淫巧。若是想学习素数筛法的可以跳过这篇题解了。

正文

相信各位都知道一个 $O(\sqrt n)$ 判断素数的方法，也就是枚举 $2\sim\lfloor\sqrt n\rfloor$ 检查每个数是否是 $n$ 的约数。具体代码如下：

bool check(int x) {
    if (x == 0 || x == 1)
        return false;
    for (int i = 2; i * i <= x; ++ i)
        if (x % i == 0)
            return false;
    return true;
}

这个题我们只要对于每个询问都这样判断一次即可，复杂度上界 $O(M\sqrt N)$，可以通过此题。（所以说加强数据啊！）

但是如果我的数据是 $10^6$ 个 $9840769$，并且你的程序没有记忆化，刚刚通过此题的程序需要 7.7s 左右的时间才能出解。我们考虑怎样优化。

我们判断约数的时候需要取模，而众所周知取模操作是很慢的，如果能加快取模的效率，就能对运行速度有很大优化。

Min_25 在他的博客里讲到了这样一种优化方法：

考虑到判断约数时我们只需要得知取模结果是否为 $0$，并不需要知道实际结果。

若 $m$ 为奇数，$m'\cdot m\equiv1\pmod{2^{64}}$，且有 $n\in\left[0,2^{64}\right)$，则：

$$ n\equiv0\pmod{m}\ \Leftrightarrow\ (n\cdot m')\bmod{2^{64}}\leqslant\lfloor\frac{2^{64}}{m}\rfloor $$

对于一个模数 $m$ 我们预处理出 $m'$ 和 $\lfloor\frac{2^{64}}{m}\rfloor$，然后我们就可以把判断 $n\bmod{m}$ 是否为 $0$ 转化为一次乘法和一次比较大小。

使用这个方法，刚刚跑 7.7s 的程序只需要 1.9s 即可出解，$4$ 倍的效率优化！

最后

这个技巧不仅可以用于判断素数，也可以用于质因数分解，杜教筛、洲阁筛、Min_25 筛的预处理。虽然可以使用的场合并不算很广，不过效率优化还是十分明显的！

Pixiv 96280070 p6

最后修改：2022 年 02 月 28 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏