萌新尚菜,勿喷
提个很 sb 的问题:不看复杂度,min25 筛在用途上是否能覆盖杜教筛?(如果是的话就能少学一个算法了)
有一类题最后是要求 ∑i⌊ni⌋f(i)\sum_i\left\lfloor\dfrac ni\right\rfloor f(i)∑i⌊in⌋f(i),其中 f(i)f(i)f(i) 是积性函数,一般整除分块然后需要求 fff 的区间和,转化为前缀和然后 min25 筛要做 O(n)\mathrm O(\sqrt n)O(n) 次(肯定爆炸),而杜教筛能顺便记录所有 ⌊ni⌋\left\lfloor\dfrac ni\right\rfloor⌊in⌋ 处的前缀和,只要做一次。这么看 min25 筛似乎不能解决这类问题?