2012-05-07 14:35:52Morris

[UVA][Math] 11526 - H(n)

Problem G
H(n)
Input: Standard Input

Output: Standard Output

 

What is the value this simple C++ function will return?

 

long long H(int n){

      long long res = 0;

     for( int i = 1; i <= n; i=i+1 ){

            res = (res + n/i);

      }

     return res;

}

 

Input
The first line of input is an integer T ( T <= 1000 ) that indicates the number of test cases. Each of the next T line will contain a single signed 32 bit integer n.

 

Output
For each test case, output will be a single line containing H(n).

 

Sample Input                      Output for Sample Input

2

5

10

 

10

27

 




事實上, 我用模擬的方式來寫, 不過可以估算的是, 大概是在 Sqrt(N) 左右的時間,
但由於黑心的負數, 我吃了好多怪怪的 WA, 又由於是模擬中間運算多了很多除法,
時間跑得太慢了

//ANSI C 0.632
#include <stdio.h>
#include <math.h>

int main() {
    int t, n;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        if(n <= 0) {
            puts("0");
            continue;
        }
        long long ans = 0;
        int j, k = n, l, r;
        for(j = 1; ;) {
            r = n/j, l = n/(j+1);
            ans += (long long)j*(r-l);
            k -= r-l;
            if(k == 0)  break;
            j = n/k;
        }
        printf("%lld\n", ans);
    }
    return 0;
}