关于杜教筛和 min25 筛
  • 板块学术版
  • 楼主chenxia25
  • 当前回复19
  • 已保存回复19
  • 发布时间2021/2/16 17:45
  • 上次更新2023/11/5 03:12:10
查看原帖
关于杜教筛和 min25 筛
138400
chenxia25楼主2021/2/16 17:45

萌新尚菜,勿喷

提个很 sb 的问题:不看复杂度,min25 筛在用途上是否能覆盖杜教筛?(如果是的话就能少学一个算法了)

有一类题最后是要求 inif(i)\sum_i\left\lfloor\dfrac ni\right\rfloor f(i),其中 f(i)f(i) 是积性函数,一般整除分块然后需要求 ff 的区间和,转化为前缀和然后 min25 筛要做 O(n)\mathrm O(\sqrt n) 次(肯定爆炸),而杜教筛能顺便记录所有 ni\left\lfloor\dfrac ni\right\rfloor 处的前缀和,只要做一次。这么看 min25 筛似乎不能解决这类问题?

2021/2/16 17:45
加载中...