Problem 11526 H(n)

本來我以為這題會很難，因為老老實實的用暴力法做絕對超過時間，而且它也說它會拿 1000 個測試資料來嚇人，所以不能用暴力法。所以我上論壇看了一下，才知道解法，我引用一下：
原網址連結

「for n = 10; go along the similar way:

  lets say n = 10;
  k = 1;  sum = 0;
  so, 10/1 = 10

  k = 2
  and 10/2 = 5
  so, for all  the integer divisions, all i = 6 to 10 
  will produce n/i = 1; (last denominator)
  so, you don't need to calculate for 6 to 10, you have
  5x1 + 10/1 = 15; (for k = 1) sum = 15;

  k = 3
  again 10/3 = 3
  so,  for all the integer divisions, all i = 4 to 5 
  will produce n/i = 2;  (last denominator)
  so, you don't need to calculate for 4 to 5, you  have
  2x2 + 10/2 = 9; (for k = 2) sum = sum + 9 = 24;

  as k is  the largest within sqrt(10);
  so last we count for k = 3; for 3, one  thing here to
  note that, 10/3 is also 3, 
  so, in such cases, we have to  consider once, cause 
  otherwise it will be counted twice.
  so, sum =  sum + 3 = 27(ans)

  for 10, we have the values (imagine RED is not  yet 
  counted, and GREEN is already counted, and BLUE is 
  the current term)
  k  = 1; (10) + 5 + 3 + 2 + 2 + (1 + 1 + 1 + 1 + 1)
  k = 2; 10 + (5) + 3 + (2 + 2) + 1 + 1 + 1 + 1 + 1
  k = 3; 10 + 5 + (3)  + 2 + 2 + 1 + 1 + 1 + 1 + 1;
  so you see, 3 is to be counted once as it 
  has no separate counterpart.
  if  k==n/k then you need to count once;」

依據以上解說，相信非常的清楚，所以寫成 C 語言成式如下：

scanf("%ld", &n);
Hn = 0;
sqrtN = (int)sqrt(n);
for (i = 1; i <= sqrtN; i ++)
{
    count = (n/i) - (n/(i + 1));
    if (i == n / i) Hn += (n / i);
    else Hn += i * count + (n / i);
}
printf("%ld\n", Hn);

By David.K

p11526題目連結
回ACM題庫目錄
回首頁