关于杜教筛的时间复杂度
  • 板块学术版
  • 楼主weilycoder
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/5/6 11:19
  • 上次更新2024/5/6 16:34:10
查看原帖
关于杜教筛的时间复杂度
818693
weilycoder楼主2024/5/6 11:19

在数论分块处理

−∑i=2g(i)S(⌊ni⌋)-\sum_{i=2}g(i)S\left(\left\lfloor\dfrac{n}{i}\right\rfloor\right)

的时候,如果 g(i)g(i) 的前缀和继续用杜教筛处理(例如:g(n)=μ(n)g(n)=\mu(n)),总的时间复杂度将会是多少?

PS:我自己测试 10910^9 的数据在洛谷上吸氧大约跑 250ms250ms,说明仍低于线性。

2024/5/6 11:19
加载中...