@[rhn7](/user/760998) 杜教筛 + 整除分块，可以做到 $\Theta(n^{2/3})$。
by 飞雨烟雁 @ 2024-04-12 22:20:07
@[rhn7](/user/760998) 整除分块之后暴力单点求 $\varphi$ 就是 $O(n^{\frac{3}{4}})$ 的吧
by rui_er @ 2024-04-12 22:20:28
@[飞雨烟雁](/user/375984) 大佬能说得具体一点吗，没学过杜教筛，只听说能求 $\sum_{i=1}^{n}\varphi(i)$，怎么求 $\sum_{i=1}^{n}\varphi(\frac{n}{i})$
by rhn7 @ 2024-04-12 22:26:49
@[rhn7](/user/760998) 用不着杜教筛，预处理一部分应该也能 $O(n^{\frac{2}{3}})$
by rui_er @ 2024-04-12 22:27:21
@[rui_er](/user/122461) 套上整除分块后复杂度不变吧，因为他会复用很多东西
by Rain_chr @ 2024-04-12 22:28:04
@[rui_er](/user/122461) 啊，怎么预处理
by rhn7 @ 2024-04-12 22:28:30
@[rui_er](/user/122461) @[rhn7](/user/760998) 想错了，用不了杜教筛，预处理前 $B$ 个 $\varphi(k)$，对于大于 $B$ 的 $\varphi(k)$，我们可以在 $\Theta(\sqrt k)$ 时间内求出。
时间复杂度为：
$$B+\sum_{k=1}^{n/B}\sqrt {n/k}\approx B+n/\sqrt B$$
取 $B=\Theta(n^{2/3})$ 即得 $\Theta(n^{2/3})$ 的做法。
by 飞雨烟雁 @ 2024-04-12 22:32:31
@[rhn7](/user/760998) <https://www.luogu.com.cn/paste/2swwkpf0>
sb 洛谷告诉我未按规范排版代码，我不知道为什么。
by rui_er @ 2024-04-12 22:35:04
@[飞雨烟雁](/user/375984) 谢谢！
by rhn7 @ 2024-04-12 22:36:24
整除分块 + 暴力单点求 $\varphi$ 可做到 $O(n^{3/4})$。
在此基础上可作优化：
取阈值 $B=n^{2/3}\log^{-1/2}n.$
对于 $n/i\le B$ 的部分线性筛 + 整除分块计算。
对于 $n/i>B$ 即 $i<n/B$ 的部分，考虑通过枚举根号级别以内的质数来分解每个 $n/i$，从而完成计算。
复杂度为 $\displaystyle O\left(B+\sum_{p^2\le B}\dfrac nB+\sum_{B<p^2\le n}\dfrac n{p^2}\right)=O(n^{2/3}\log^{-1/2}n).$
by XeCtera @ 2024-04-12 22:40:00