链接：LightOJ - 1245 Harmonic Number (II)
题意：
给出 T ( ≤ 1000 ) T(\le1000) T(≤1000)个 n ( 1 ≤ n ≤ 2 31 ) n(1\le n\le2^{31}) n(1≤n≤231)，每次求解 H ( n ) = ? n 1 ? + ? n 2 ? + ? + ? n n ? H(n)=\lfloor \frac{n}{1}\rfloor+\lfloor\frac{n}{2}\rfloor+\dots+\lfloor\frac{n}{n}\rfloor H(n)=?1n??+?2n??+?+?nn??
分析：
对于 ? n i ? \lfloor \frac{n}{i}\rfloor ?in??求和，实际上 ? n i ? \lfloor \frac{n}{i}\rfloor ?in??只有至多 ? 2 n ? \lfloor 2\sqrt n\rfloor ?2n??种取值。
对于任意 i ≤ n i\le n i≤n，需要找到一个最大的 j ≤ n j\le n j≤n，使得 ? n i ? = ? n j ? \lfloor \frac{n}{i}\rfloor=\lfloor \frac{n}{j}\rfloor ?in??=?jn??，则有：
j = ? n ? n i ? ? j=\left\lfloor \frac{n}{\lfloor \frac{n}{i}\rfloor}\right \rfloor j=??in??n??
所以当从小到大枚举 i i i，则 ? n i ? \lfloor \frac{n}{i}\rfloor ?in??的个数为 j ? i + 1 j-i+1 j?i+1个，求和的时间复杂度为 O ( ? 2 n ? ) O(\lfloor 2\sqrt n\rfloor) O(?2n??)。
以下代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int main()
{
int T,kase=0;scanf("%d",&T);LL n;while(T--){
scanf("%lld",&n);LL i=1,j,ans=0;while(i<=n){
j=n/(n/i);ans+=(n/i)*(j-i+1);i=j+1;}printf("Case %d: %lld\n",++kase,ans);}return 0;
}