这题 n 是不是可以开到 1e9

如题。

式子是 $-\frac{n(n+1)}{2}+\sum_{i=1}^{n} i S(\lfloor\frac{n}{i}\rfloor)$，其中 $S(n)$ 是欧拉函数 $\varphi (n)$ 的前缀和。

这个式子可以直接通过本题，但是这个东西是可以数论分块的。

如果开成 $1 \le n \le 10^9$，预处理 $S(n)$ 到 $10^7$ 空间是不会炸的，再往上可以杜教筛，需要上杜教筛的 $S(\lfloor\frac{n}{i}\rfloor)$ 不超过 $100$ 个，$O(n^{2/3} \times 100)$ 大概可以承担。