藍橋杯 C 語言入門：序列求和 (大數據範圍長整數溢位陷阱)

藍橋杯 入門訓練 - 序列求和：數學公式優化與長整數型別選擇

題目：輸入整數 n (1 ≤ n ≤ 1,000,000,000)，輸出 1 + 2 + ... + n 的值。
樣例：4 → 10，100 → 5050。

暴力迴圈會超時

// 錯誤示範：O(n) 時間複雜度
long long sum = 0;
for (long long i = 1; i <= n; i++) sum += i; // n=1e9 约需数秒，超時

當 n = 1,000,000,000，迴圈執行十億次，在典型 1-2 秒時限內無法完成。

數學公式 O(1) 解法

等差數列求和公式：S = n * (n + 1) / 2

• 先乘後除避免小數，但 n*(n+1) 可能溢位 32 位元 int (最大 ~21 億)。
• n=1e9 → n*(n+1) ≈ 1e18，需 64 位元有號整數 (long long / int64_t)。

完整標準 C 代碼

#include 
#include  // PRIu64, PRId64 跨平台格式宏

int main() {
    long long n;
    if (scanf("%lld", &n) != 1) return 1; // 讀取失敗
    // 使用長整數運算，避免中間結果溢位
    long long result = n * (n + 1) / 2;
    printf("%lld\n", result); // Windows MSC: %lld / %I64d；GCC/Clang: %lld
    return 0;
}

跨平台輸出格式說明

關鍵知識點總結

1. 演算法複雜度：O(n) → O(1) 是解決大數據範圍的核心。
2. 資料型別範圍：int (32-bit) 約 ±2.1×10⁹；long long (64-bit) 約 ±9.2×10¹⁸，足容納 n=1e9 的結果 (5×10¹⁷)。
3. 輸入驗證：實務中應檢查 scanf 回傳值。
4. 測試邊界：n=1 → 1，n=1,000,000,000 → 500000000500000000。

此題是「數學優化 + 型別選擇」的經典入門組合，牢記公式與 long long 即可輕鬆通過。