H(n)
原先的博客写的很乱，这里重新写一下，应该是一般初中生可以看懂的水平了。
题意即求取：
\[\sum _ { i = 1 } ^ { n } \left\lfloor \dfrac{n}{i} \right\rfloor \]也就是整除分块。
这个想法的原理来自于：\(\lfloor n/i \rfloor\) 的取值数量不超过 \(O(\sqrt{n})\)。
证明：
对于 \(i\le \sqrt{n}\)，有 \(O(\sqrt{n})\) 种取值。
对于 \(i>\sqrt{n}\)，必有 \(n/i<\sqrt{n}\)，故亦只有 \(O(\sqrt{n})\) 种取值。
所以对于值相同的，我们打包计算，就可以有效降低复杂度。
第二个基本想法是，\(\lfloor n/i\rfloor\) 的值相同的 \(i\) 一定紧密相邻地处在一个区间中。这个是容易理解的。
对于第一个这样的区间 \(\left[i,j\right]\)，我们必然知道 \(i = 1\)，接下来就需要通过 \(i\) 求出 \(j\)，而下一个区间的起始正是 \(j+1\)。
至于怎样通过 \(i\) 求出 \(j\) 呢？我更倾向于直接说做法后给出证明：
\[j= \left\lfloor \dfrac {n} {\left\lfloor\dfrac{n}{i}\right\rfloor}\right\rfloor \]欲证：\(\left\lfloor n / j\right\rfloor = \left\lfloor n / i\right\rfloor\) 且 \(\left\lfloor n / (j+1)\right\rfloor < \left\lfloor n / i\right\rfloor\)
证明：
我们有：
\[\left\lfloor\dfrac{n}{i}\right\rfloor \le\dfrac{n}{i} < \left\lfloor\dfrac{n}{i}\right\rfloor + 1 \]所以：
\[j = \left\lfloor \dfrac {n} {\left\lfloor\dfrac{n}{i}\right\rfloor}\right\rfloor \ge \left\lfloor i\right\rfloor = i \\ j =\left\lfloor \dfrac {n} {\left\lfloor\dfrac{n}{i}\right\rfloor}\right\rfloor \le \dfrac {n} {\left\lfloor\dfrac{n}{i}\right\rfloor} \]所以：
\[\left\lfloor\dfrac{n}{j}\right\rfloor \ge \left\lfloor\left\lfloor\dfrac{n}{i}\right\rfloor\right\rfloor = \left\lfloor\dfrac{n}{i}\right\rfloor \\ \left\lfloor\dfrac{n}{j}\right\rfloor\le \left\lfloor\dfrac{n}{i}\right\rfloor \]从而得到：
\[\left\lfloor\dfrac{n}{j}\right\rfloor = \left\lfloor\dfrac{n}{i}\right\rfloor \]又：
\[j+1=\left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{i}\right\rfloor}\right\rfloor+1>\dfrac{n}{\left\lfloor\dfrac{n}{i}\right\rfloor} \]所以：
\[\left\lfloor\dfrac{n}{j+1}\right\rfloor \le \dfrac{n}{j+1} < \left\lfloor\dfrac{n}{i}\right\rfloor \]\(\mathcal{Q.E.D.}\)
那么剩下就是每部分打包提取之类的了。
时间复杂度是 \(O(\sqrt{n})\) 的。
这一部分的代码如下：
inline ll Get(ll n) {
ll res=0;
for(ll i=1,j;i<=n;i=j+1) {
j=n/(n/i);res+=(j-i+1)*(n/i);
}
return res;
}
那么对于更为一般的形式：
\[\sum _ { i =1 } ^ {n} f(i) \left\lfloor\dfrac{n}{i}\right\rfloor \]我们又应该如何求取？
其实很简单，定义 \(f\) 的前缀和 \(S\)，使得：
\[S(n) = \sum _ { i = 1 } ^ {n} f(i) \]那么我们的代码就可以写成这样：
inline ll Get(ll n) {
ll res=0;
for(ll i=1,j;i<=n;i=j+1) {
j=n/(n/i);res+=(s[j]-s[i-1])*(n/i);
}
return res;
}
一般在数值较大时会取模，这里不作赘述。
那么对于多维的情况又该如何？
\[\sum _ { i = 1 } ^ {\min \{ n , m\}} f(i) \left\lfloor\dfrac{n}{i}\right\rfloor\left\lfloor\dfrac{m}{i}\right\rfloor \]实际上代码只要这样写就可以了：
inline ll Get(ll n) {
ll res=0;
for(ll i=1,j;i<=n&&i<=m;i=j+1) {
j=min(n/(n/i),m/(m/i));res+=(s[j]-s[i-1])*(n/i)*(m/i);
}
return res;
}
正确性是显然的。
相当于我们只看每个区间的分界线，然后两个相邻的分界线之间的数打包带走。
时间复杂度是 \(O(k\sqrt{n})\) 的（其中 \(k\) 是维数）。
再写一个你们大概率用不到的结论：
\[\sum _ { i = 1 } ^ { n } \sigma _ 0 (i) = \sum _ { i =1 } ^ {n} \sum _ {d\mid i} 1 = \sum _ { d =1 } ^ { n } \sum _ {i = 1 } ^ {\lfloor n / d\rfloor} 1 = \sum _ {i = 1 } ^ {n}\left\lfloor \dfrac{n}{i}\right\rfloor = H(n) \]代码（本题的 AC 代码）：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define ll long long
using namespace std;
namespace Ehnaev{
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
}using Ehnaev::read;using Ehnaev::write;
inline void writeln(ll x) {write(x);putchar(10);}
ll T,n;
inline ll Get(ll n) {
ll res=0;
for(ll i=1,j;i<=n;i=j+1) {
j=n/(n/i);res+=(j-i+1)*(n/i);
}
return res;
}
int main() {
T=read();
while(T--) {
n=read();writeln(Get(n));
}
return 0;
}