本文共 1717 字，大约阅读时间需要 5 分钟。
题目链接：
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
题目翻译：
求n/1+n/2+n/3+n/4+......+n/n的和。
规律题，需要自己手推一下公式，有点难想。（题解来自网上，比较好懂）
先求出前sqrt(n)项和：即n/1+n/2+...+n/sqrt(n)
再求出后面所以项之和.后面每一项的值小于sqrt(n),计算值为1到sqrt(n)的项的个数，乘以其项值即可快速得到答案 例如:10/1+10/2+10/3+...+10/10 sqrt(10) = 3 先求出其前三项的和为10/1+10/2+10/3 再求出值为1的项的个数为(10/1-10/2)个，分别是(10/10,10/9,10/8,10/7,10/6),值为2个项的个数（10/2-10/3）分别是（10/5,10/4）,在求出值为3即sqrt(10)的项的个数. 显然，值为sqrt(10)的项计算了2次,减去一次即可得到答案。当n/(int)sqrt(n) == (int)sqrt(n)时，值为sqrt(n)的值会被计算2次。样例分析：
n = 10，sqrt(10) = 3，10/sqrt(10) = 3i 1 2 3 4 5 6 7 8 9 10n/i 10 5 3 2 2 1 1 1 1 1m=n/isum += m;m = 1的个数10/1-10/2 = 5；m = 2的个数10/2-10/3 = 2；m = 3的个数10/3-10/4 = 1；
代码实现：
#include#include #define ll long longusing namespace std;int main(){ int T,kcase=1; ll n,i; scanf("%d",&T); while(T--){ scanf("%lld",&n); ll ans=0,m=(ll)sqrt(n); for(i=1;i<=m;++i){ ans+=n/i; ll l=n/i; ll r=n/(i+1); if(l>r) ans+=(l-r)*i; } if(n/m==m)//重复计算的减去 ans-=m; printf("Case %d: %lld\n",kcase++,ans); } return 0;}
转载地址：http://wgymz.baihongyu.com/