LightOJ - 1245 - Harmonic Number (II)（数学）

链接：

https://vjudge.net/problem/LightOJ-1245

题意:

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.

思路：

考虑对整数n/i的上下限，下限为最大值为n/(n/i))。不断循环，相等的值直接跳过去就不会超时了。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<math.h>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

const int INF = 1e9;

const int MAXN = 1e7+10;

const int MOD = 1e9+7;

LL n;

int main()

{

    int t, cnt = 0;

    scanf("%d", &t);

    while(t--)

    {

        printf("Case %d:", ++cnt);

        scanf("%lld", &n);

        LL p = 1;

        LL sum = 0;

        while(p <= n)

        {

            LL tmp = n/p;

            LL next = n/(n/p);

            sum += 1LL*tmp*(next-p+1);

            p = next+1;

        }

        printf(" %lld\n", sum);

    }

    return 0;

}