在数论分块处理
−∑i=2g(i)S(⌊ni⌋)-\sum_{i=2}g(i)S\left(\left\lfloor\dfrac{n}{i}\right\rfloor\right)−∑i=2g(i)S(⌊in⌋)
的时候,如果 g(i)g(i)g(i) 的前缀和继续用杜教筛处理(例如:g(n)=μ(n)g(n)=\mu(n)g(n)=μ(n)),总的时间复杂度将会是多少?
PS:我自己测试 10910^9109 的数据在洛谷上吸氧大约跑 250ms250ms250ms,说明仍低于线性。