题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3944

题意：欧拉函数，莫比乌斯函数前缀和，\(n\leq 2^{31}-1\)

---

人生中的第一次杜教筛= =

n 很大，显然不能线性筛了。现在只考虑莫比乌斯函数的前缀和，欧拉函数同理。

构造这么几个函数：

$$g(n)=\sum_{i=1}^{n}\mu (i)$$

$$f(n)=\sum_{d|n}^{ }\mu (d)$$

$$F(n)=\sum_{i=1}^{n}f(i)$$

很显然，\(F(n)=1+0+0+...+0=1\)。

另外，\(F(n)=\sum_{i=1}^{n}\mu (i)\cdot \left \lfloor \frac{n}{i} \right \rfloor=\sum_{i=1}^{n} g(\left \lfloor \frac{n}{i} \right \rfloor)\)

这是为什么呢，想想就知道，比如\(\mu (1)\) 出现了\(n\) 次，在每个\(g(\frac{n}{i})\) 中都出现了，\(\mu (2)\) 只出现了\(\left \lfloor \frac{n}{2} \right \rfloor\) 次，仅在\(\left \lfloor \frac{n}{i} \right \rfloor\geq 2\) 的\(g\) 中出现了，以此类推。

所以\(\sum_{i=1}^{n}g(\left \lfloor \frac{n}{i} \right \rfloor)=1\)，那么\(g(n)=1-\sum_{i=2}^{n}g(\left \lfloor \frac{n}{i} \right \rfloor)\)

这玩意递归求解即可，但是直接上会 T。我们可以预处理出一些 n 比较小的前缀和，可以证明的是，预处理到\(n^{\frac{2}{3}}\) 处是最优的。