UOJ Logo luosiyuan的博客

博客

[详细揭秘] min_25 筛的卡常技巧

2021-04-07 22:12:28 By luosiyuan

https://uoj.ac/submission/467792 这份提交中最大的点只用了 440ms,总时间直接比最快的非打表提交快了 1500ms,这是怎么做到的呢?下面小编带大家来了解一下吧!

所谓卡常技巧,其实就是把所有除法(除了算 pos 的一个)改成了实数乘法而已,注意到除数只可能是小于 $\sqrt n$ 的质数,因此可以预处理出来。大家可能会很惊讶,实数乘法怎么会这么快呢?事实就是这样,小编也很惊讶。

这就是关于 min_25 筛的卡常的事情了,大家有什么想法呢,欢迎在评论区告诉小编一起讨论哦!

评论

skip2004
其实和 Barrett Reduction 是一样的,不过这可能确实是一种容易实现的方法
zhltao
但是似乎在loj机子上没有什么区别?[用了double](https://loj.ac/s/1150197) [没用double](https://loj.ac/s/1150166) 并没有显著差别。是我的姿势不对吗?求解答qaq

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。