模板

终于知道发明者的正确的名字了,是Min_25,这个筛法速度为亚线性的(O(frac{n^{frac{3}{4}}}{log x})),用于求解具有下面性质的积性函数的前缀和:

  1. (p) 处是简单的低次多项式
  2. (p^c) 处可以快速求值

貌似积性函数是指取一个积性函数 (f(x)) ,其在质数的位置上取值与所求函数相同。所以可以用来求n以内的质数的个数(取常函数 (f(x)=1) )以及质数的和(取恒等函数 (f(x)=x) )。

参考资料:

loj#6235. 区间素数个数(min25筛) - 自为风月马前卒 - 博客园
关于min_25筛的一些理解 - GuessYCB - 博客园
2019徐州网络赛 H.function - heyuhhh - 博客园

原文地址:https://www.cnblogs.com/KisekiPurin2019/p/11806890.html