此题解自 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})\)。足以通过本题。