UVa 11526 - H(n)

Contents

1. 1. Problem
2. 2. Solution
3. 3. Code

Problem

題目網址
中文網址

Solution

參考：http://using-c.blogspot.tw/2010/04/problem-11526-hn.html

將 n/i 結果一樣的一起計算。
以 n = 10 來說：
$$\frac{10}{1} = 10 => \frac{10}{10} = 1$$
$$\frac{10}{2} = 5 => \frac{10}{5} = 2$$
可以得出在 ${5}\lt{i}\le{10}$ 結果會等於 1 ，以此類推下去 ${3}\lt{i}\le{5}$ 會等於 2。
最後則是要注意當 $$\frac{10}{3} = 3$$ 這種狀況時，${2}\lt{i}\le{3}$ 要避免重複算到自己。

Code

UVa 11256

#include <cstdio>
#include <cmath>
typedef long long LL;

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n, sqrt_n;
        scanf("%d", &n);
        sqrt_n = sqrt(n);

        LL sum = 0;

        for (int i = 1; i <= sqrt_n; i++)
        {
            int temp = n / i;
            int count = temp - n / (i + 1);
            sum += (LL)i * count + (temp == i ? 0 : temp); //避免重複計算
        }

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

    return 0;
}