@ACの666

感谢投稿，有待改进：

杜教筛复杂度证明如下：

首先，数论分块$O(\sqrt{n})$的证明：对于$\lfloor \frac{n}{i}\rfloor$，当$i\leq \sqrt{n}$时有$O(\sqrt{n})$种，当$i>\sqrt{n}$时$\lfloor \frac{n}{i}\rfloor\leq \sqrt{n}$有$O(\sqrt{n})$种

杜教筛的复杂度即$T(n)=\sum_{i=1}^{\sqrt{n}}\sqrt{i}+\sqrt{\frac{n}{i}}$

$T(n)<\int_1^{\sqrt{n}}(\sqrt{i}+\sqrt{\frac{n}{i}}) di=O(n^{3/4})$

所以裸的杜教筛复杂度为$O(n^{3/4})$

现在有个优化叫做“前$S$项$(S>\sqrt{n})$线性预处理"。此时杜教筛复杂度变成了：$T(n)=\sum_{i=1}^{n/S} \sqrt{ \frac{n}{i}}$

$T(n)<\int_1^{\sqrt{n/S}} \sqrt{\frac{n}{i}} di =O(n/\sqrt{S})$

总复杂度为$O(S+\frac{n}{\sqrt{S}})$，当$S=n^{2/3}$时复杂度为最优，即$O(n^{2/3})$

同时，理解了数论分块的基本原理后，可以不用任何哈希表记忆化。所有会出现的都是$\lfloor \frac{n}{i} \rfloor$，所以可以开一个两倍根号的数组，按根号分配。即假设要搞Getsum(x).若$x\leq \sqrt{n}$，返回$dp[x]$；否则返回$dp[n/x+\sqrt{n}]$大概这样

另：杜教筛在寻找那个函数的过程中可以只考虑单个质数的函数构造，这样更方便...

另注：积分不会算就去wolframalpha.com嘛...