整除分块套杜教筛为什么是 O(n^2/3) 的

假设我们要筛一个东西叫做 \(f\) .

记

\[D(n)=\left\{n,\left\lfloor\dfrac n2\right\rfloor,\left\lfloor\dfrac n3\right\rfloor,\left\lfloor\dfrac n4\right\rfloor,\cdots\right\}
\]

那么我们知道杜教筛在计算 \(f(n)\) 时实际上是对 \(D(n)\) 中的所有数都计算了一遍 \(f(n)\) 并存入了缓存 .

然而我们整除分块的过程就是求 \(D(n)\) 里面这些东西，所以说实际上只筛了一次 \(f\)，其他全部在查表 .

于是复杂度是 \(O(n^{2/3})\) .

巴特西