求助杜教筛时间复杂度
查看原帖
求助杜教筛时间复杂度
38785
XeCtera楼主2020/5/13 12:23

如果线性筛预处理 1k1\sim k 的答案,TT 组数据,那么时间复杂度是不是 O(k+T×nk)O\left(k+T\times\dfrac{n}{\sqrt k}\right)

如果是,为什么 kk21474836472/32147483647^{2/3}214748364702/321474836470^{2/3} 跑得快,是因为数据水/常数问题吗
如果不是,求正确的时间复杂度

2020/5/13 12:23
加载中...