lightoj 1245

lightoj 1245 Harmonic Number (II)

题意：给定一个 n ，求 n/1 + n/2 + …… + n/n 的值(这里的 "/" 是计算机的整数除法，向下取整)。

思路：唉，想了很久，最终还是没什么好方法。我的思路是这样的：

　　　　记录结果为 n/1，n/2，……，n/n 的有多少个，然后乘以各自的值就得到结果了。唉暴搞的人桑不起，2.2s过了，膜拜 oj 里边 100+ms过的大神。

代码：

 1 #include <iostream>
 2 #include <stdio.h>
 3 using namespace std;
 4 
 5 typedef long long LL;
 6 
 7 int main()
 8 {
 9     LL a, b, n, m, i, ans;
10     int CASE, j = 1;
11     scanf("%d", &CASE);
12     while(CASE--)
13     {
14         ans = 0;
15         scanf("%lld", &n);
16         for(i = 1; i <= n; i = b + 1)
17         {
18             a = n/i , b = n/a;        //计算 a 相等时 b到达的位置，所以总数就有 (b - i + 1) 个
19             ans += a * (b-i+1) ;    //计算相等 a 的个数和
20         }
21         printf("Case %d: %lld
", j++, ans);
22     }
23     return 0;
24 }