数学原理详解

本题要求计算和式 $\sum_{i=1}^n f(i)$， 其中 $f(i)$ 表示正整数 $i$ 的约数个数。直接对每个 $i$ 计算约数个数再求和的方法时间复杂度为 $O(n \sqrt{n})$，当 $n$ 较大时（如 $n \leq 10^6$）效率较低。因此，我们需要一种更高效的数学方法。

关键变换：交换求和顺序

考虑所有从 $1$ 到 $n$ 的整数，每个数 $i$ 的约数个数 $f(i)$ 可以理解为所有能整除 $i$ 的约数 $k$ 的个数。

因此，原和式可以重写为：

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

$k \mid i$ 就是k ​​整除​​ i

这里内层求和表示对每个 $i$，计算其约数的个数。现在，我们交换求和顺序：改为先固定约数 $k$，然后计算 $k$ 作为约数出现在多少个 $i$ 中（其中 $i \leq n$）。由于 $k$ 是 $i$ 的约数当且仅当 $i$ 是 $k$ 的倍数，因此对于每个 $k$，满足 $k \mid i$ 且 $i \leq n$ 的 $i$ 的个数就是 $k$ 的倍数中不超过 $n$ 的个数，即 $\left\lfloor \frac{n}{k} \right\rfloor$。

换句话说：

-$\left\lfloor \frac{n}{k} \right\rfloor$ 正是$k$ 在范围$1$ 到$n$ 中作为约数出现的次数（即“有效的个数”）。例如，如果$k=2$ 和$n=5$，那么$2$ 的倍数有$2, 4$，所以出现了 2 次，而$\left\lfloor \frac{5}{2} \right\rfloor = 2$。

因此，求和$\sum_{k=1}^n$$\left\lfloor \frac{n}{k} \right\rfloor$ 实际上是在对所有可能的约数$k$ 计算其出现的频次，从而等价于原问题。这种变换是数论中常见的技巧，称为“除数求和”或“交换求和顺序”。

因此，原和式等价于：

$\sum_{i=1}^n f(i)$= $\sum_{k=1}^n$$\left\lfloor \frac{n}{k} \right\rfloor$

这个变换将问题转化为计算所有 $k$ 从 $1$ 到 $n$ 的 $\left\lfloor \frac{n}{k} \right\rfloor$ 之和。

效率分析

直接计算新和式的时间复杂度为 $O(n)$，对于 $n \leq 10^6$ 是可行的。但还可以进一步优化：由于 $\left\lfloor \frac{n}{k} \right\rfloor$ 的值对于连续的 $k$ 可能相同，我们可以找到使值相同的区间，批量计算。具体来说，对于每个 $k$，存在最大的 $m$ 使得

$\left\lfloor \frac{n}{k} \right\rfloor$ =$\left\lfloor \frac{n}{m} \right\rfloor$，则 $m=⌊\frac{n}{⌊n /k⌋}⌋$。

这样，求和的时间复杂度可降为 $O(\sqrt{n})$。但对于本题范围，直接循环 $k$ 从 $1$ 到 $n$ 也已足够。

样例验证

取输入样例 $n = 3$：

• 直接计算：
• $f(1) = 1$，$f(2) = 2$，$f(3) = 2$，
• 和为 $1 + 2 + 2 = 5$。
• 用新方法：
• $\left\lfloor \frac{3}{1} \right\rfloor = 3$，$\left\lfloor \frac{3}{2} \right\rfloor = 1$，$\left\lfloor \frac{3}{3} \right\rfloor = 1$，
• 和为 $3 + 1 + 1 = 5$。结果一致。