题意
根据题目给的代码，不难看出这是让我们求：
(sumlimits_{i=1}^{n}lfloor frac{n}{i} floor)
题解
整除分块模板题。
一看数据范围，发现用暴力肯定会超时。我们发现加数中有许多是相同的，并且这些加数单调不增（即相同加数必定在一起）。如果找出每段相同加数的长度，就能很快得到答案。
也就是说，如果对于一个 (i)，能找出最大的 (j) 使得 (lfloor frac{n}{i}
floor=lfloorfrac{n}{j}
floor)
，这一段的和即为 (lfloorfrac{n}{i}
floor(j-i+1))。
根据向下取整的性质，可得 (lfloor frac{n}{i} floorlefrac{n}{j}<lfloor frac{n}{i} floor+1)；
将前一个不等式变形，得 (jle frac{n}{lfloor frac{n}{i} floor})；
由于 (j) 是正整数，可得 (jle lfloorfrac{n}{lfloor frac{n}{i} floor} floor)；
所以 (j) 最大为 (iglfloorfrac{n}{lfloor frac{n}{i} floor}ig floor)。
时间复杂度为 (mathcal{O}(sqrt n))。证明如下：
-
当 (1le ile sqrt n) 时：(i) 的取值有 (sqrt n) 种，所以此时 (lfloorfrac{n}{i} floor) 的取值最多有 (sqrt n) 种。
-
当 (sqrt n< ile n) 时：(1lelfloorfrac{n}{i} floorlesqrt n)，所以 (lfloorfrac{n}{i} floor) 的取值最多有 (sqrt n) 种。
也就是说，(lfloorfrac{n}{i} floor) 的取值最多有 (2sqrt n) 种，所以时间复杂度为 (mathcal{O}(sqrt n))。
(T) 组数据，时间复杂度 (mathcal{O}(Tsqrt n))
代码：
q = read();
for(; q; --q) {
ans = 0;
n = read();
for(i = 1; i <= n; i = j + 1) {
j = n / (n / i);
ans += (j - i + 1) * (n / i);
}
printf("%lld
", ans);
}