24h購物| | PChome| 登入
2012-05-07 14:35:52| 人氣299| 回應0 | 上一篇 | 下一篇

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

推薦 0 收藏 0 轉貼0 訂閱站台

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;
}


我要檢舉
#11526#H(n)
台長： Morris

您可能對以下文章有興趣

人氣(299) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][Knuth'sPermutation] 110 - Meta-Loopless Sorts
此分類上一篇:[UVA] 763 - Fibinary Numbers

我要回應
否 是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼：
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文