算法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)\) 的做法，代码不复杂，此处不放了。大家也可以口胡。