HDU 1001 Sum Problem：求 1+2+...+n 的高效解法與避坑指南

題目大意

輸入多行整數 n (每行一個)，對每個 n 輸出 SUM(n) = 1 + 2 + ... + n，結果後空一行。結果保證在 32 位有符號整數範圍內。

樣例

Input:
1
100

Output:
1

5050

算法分析

方法一：迴圈累加 (原代碼)

while (scanf("%d", &a) != EOF) {
    sum = 0;
    for (i = 1; i <= a; i++) sum += i;
    printf("%d\n\n", sum);
}

時間複雜度：O(n) 每測試用例。缺點：大 n (如 10^7) 會超時。

方法二：等差數列求和公式 (推薦)

SUM(n) = n * (n + 1) / 2

時間複雜度：O(1)。注意：n*(n+1) 可能溢出 32 位 int，雖題目保證結果不溢出，但中間過程可能溢出。安全寫法：

long long n;
while (scanf("%lld", &n) != EOF) {
    long long sum = n * (n + 1) / 2; // long long 64位足夠
    printf("%lld\n\n", sum);
}

或利用除法先行：sum = (n % 2 == 0) ? (n/2)*(n+1) : n*((n+1)/2);

關鍵點總結

1. EOF 判斷：scanf(...) != EOF 或 ~scanf(...)。
2. 輸出格式：每個結果後 空一行 (即兩個 \n)，樣例輸出中有空行。
3. 類型選擇：用 long long 避免中間溢出，輸出用 %lld。
4. 公式優先：O(1) 公式替代 O(n) 迴圈，是 ACM 入門必備思維。

完整 AC 代碼 (C99)

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    long long n;
    while (scanf("%lld", &n) == 1) {
        long long sum = n * (n + 1) / 2;
        printf("%lld\n\n", sum);
    }
    return 0;
}

延伸思考

• 若 n 超過 64 位？需大整數庫或高精度模擬。
• 若求 1^2 + 2^2 + ... + n^2？公式 n(n+1)(2n+1)/6。
• 本題是「掛牌題」—— 只要會公式就能過，考察的是基本輸入輸出與數學建模能力。