由于题目被修改,这篇题解已经做不了这个题了。
但是这篇题解介绍的东西还是有一定意义的,有兴趣的同学仍然可以阅读一下。
题目链接: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 筛的预处理。虽然可以使用的场合并不算很广,不过效率优化还是十分明显的!
4 条评论
你的才华让人惊叹,请继续保持。 http://www.55baobei.com/CzD2vEqusS.html
你的文章让我感受到了无尽的欢乐,谢谢分享。 http://www.55baobei.com/Pv0cIVdOc0.html
你的文章让我感受到了不一样的风景,谢谢分享。http://www.rxkxmj.com
你的才华让人瞩目,期待你的更多文章。http://www.yzjgzc.com