此题解自 P1108 移植，作者：bfw

我想补充一个所谓 “推式子” 的方法。

$$\sum_{i=1}^n \sum_{j=1}^n j|i = \sum_{j=1}^n \sum_{i=1}^n j|i = \sum_{j=1}^n \lfloor \frac{n}{j} \rfloor = \sum_{i=1}^n \lfloor \frac{n}{i} \rfloor$$

整除分块，$\mathcal{O}(\sqrt{n})$ 一波带走。

算法1

暴力枚举，时间 $O(n^2)$。

算法2

利用约数数量公式。若

$$i=\sum_{j=1}^{k}{{p_j}^{a_j}}$$

则

$$f(i)=\prod_{j=1}^{k}{p_j+1}$$

其中 $p_1,p_2,\cdots ,p_k$ 是素数。

用线Doge性Doge筛筛素数，然后累乘。

这样解看起来是高明了点，但时间复杂度依然是 $O(nk)$，从这个角度看依然没有改进。

算法3

换个角度考虑。考虑 每个数作为约数的次数 。

• $1$，显然是任意一个数的约数，共出现了 $n$ 次。
• $2$，是所有被 $2$ 整除的数的约数，共出现了 $\lfloor \dfrac{n}{2} \rfloor$ 次。
• $\vdots$
• $i$，是所有被 $i$ 整除的数的约数，共出现了 $\lfloor \dfrac{n}{i} \rfloor$ 次。
• $\vdots$
• $n$，仅为 $n$ 的约数，出现了 $1$ 次。

所以

$$\sum_{i=1}^{n}{f(i)}=\sum_{i=1}^{n}{\lfloor \dfrac{n}{i} \rfloor}$$

依据此公式，得到 $O(n)$ 的做法，代码不复杂，此处不放了。大家也可以口胡。

原题就到此为止了，然鹅这道题是明显不够的。

算法 4

用整除分块（模板题：P1100），可以将复杂度降至 $O(\sqrt{n})$。足以通过本题。