具体的内容 oistream 已经说的很清楚。下面我们来证明 \(\lfloor \frac{n}{i} \rfloor\) 最多只有 \(\sqrt{n}\) 种不同的值。

对于 \(1 \leq i \leq \sqrt{n}\)，值必然不超过 \(\sqrt{n}\) 个。

对于 \(\sqrt{n} < i \leq n\)，存在 \(\lfloor \frac{n}{i} \rfloor < \sqrt{n}\)，不同的值也不超过 \(\sqrt{n}\) 个。

这样就可以说明 本质不同的值最多存在 \(2 \sqrt{n}\) 个，折合为 \(\sqrt{n}\) 个。

保证了时间复杂度是 \(\mathcal{O}(\sqrt{n})\) 的。

简单说一下除法分块是个啥：

这道题暴力显然会 T，但是 注意 \(\lfloor\dfrac{n}{i}\rfloor\) 最多只有 \(\sqrt{n}\) 种不同的值，并且相同的值是连在一起的 。这样我们可以期望一次跳过整个这一段相同的值。

假设这一段相同值区间的左端点是 \(l\)，辣么这个相同的值就是 \(\lfloor\dfrac{n}{l}\rfloor\)。而这一区间右端点是多少呢？就是 \(\lfloor\dfrac{n}{\lfloor\dfrac{n}{l}\rfloor}\rfloor\)。（仔细想想，就是 \(n\) 除以刚刚那个值然后下取整。）

也可以看做将 \([1,n]\) 剖分成了 \(\sqrt{n}\) 个块，属于分块类的算法，所以由此得名。

这样，我们就有如下核心代码（注意，这是开了 long long 的）：

for(l=1ll;l<=n;l=r+1ll)
    {
        long long t=n/l;
        r=min(n/t,n);
        sum+=(r-l+1ll)*t;
    }

其中 sum+=(r-l+1ll)*t 用来累加（就是把这一段的长度乘以值）。

然后这题是需要开 long long 的，一个好的办法是将整个程序写好之后再利用编辑器的替换功能把 int 替换成 long long，但是 main() 函数就不要替换了（