题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=98634#problem/B
Description：
I was trying to solve problem '1234 - Harmonic Number', I wrote the following code
long long H( int n ) {
long long res = 0;
for( int i = 1; i <= n; i++ )
res = res + n / i;
return res;
}
Yes, my error was that I was using the integer divisions only. However, you are given n, you have to find H(n) as in my code.
Input：
Input starts with an integer T (≤ 1000), denoting the number of test cases.
Each case starts with a line containing an integer n (1 ≤ n < 231).
Output：
For each case, print the case number and H(n) calculated by the code.
Sample Input：
11
1
2
3
4
5
6
7
8
9
10
2147483647
Sample Output：
Case 1: 1
Case 2: 3
Case 3: 5
Case 4: 8
Case 5: 10
Case 6: 14
Case 7: 16
Case 8: 20
Case 9: 23
Case 10: 27
Case 11: 46475828386
题意：通过给出的代码计算i=1~n时n/i的和。
分析：举例n=8时，m=sqrt（n），得到所有的n/i为8，4，2，2，1，1，1，1，通过找规律可以发现有8-4个1，4-2个2，那么我们发现当i为m~n之间时是有规律的，我们可以当i在1~m时暴力，m~n时通过规律计算。
#include<stdio.h> #include<string.h> #include<queue> #include<math.h> #include<stdlib.h> #include<algorithm> using namespace std; const int N=1e6+10; const int INF=0x3f3f3f3f; const int MOD=1e9+7; typedef long long LL; LL Solve(LL n) { int i, m, left, right; LL res = 0; m = (int)sqrt(n); for (i = 1; i <= m; i++) res += n/i; ///计算i=1~m的n/i和 left = right = m; ///left，right是n/i==m的数的左右区间 while (m > 0) { right = n/m; ///计算n/i==m的数的区间右端点 res += (right-left)*m; ///计算该区间的和 m--; left = right; ///更新左端点 } return res; } int main () { int T, k = 0; LL n, ans; scanf("%d", &T); while (T--) { k++; scanf("%lld", &n); ans = Solve(n); printf("Case %d: %lld ", k, ans); } return 0; }