連續正整數和分解：數學推導與 O(√n) 演算法完整實作

問題描述

給定正整數 m，找出所有長度 n ≥ 2 的連續正整數序列，使其和等於 m。輸出所有序列，按起始數遞增排序；無解輸出 "NONE"。

範例：
m=15 → 1 2 3 4 5 / 4 5 6 / 7 8
m=16 → NONE

數學推導

設序列起始為 a，長度為 n (n ≥ 2)：

m = a + (a+1) + ... + (a+n-1)
  = n*a + n(n-1)/2
→ a = m/n - (n-1)/2

條件：

1. a 為正整數 → m/n - (n-1)/2 ≥ 1 且為整數
2. n ≥ 2

n 的上界估算

最小起始數 a=1 時，和最大：

n(n+1)/2 ≤ m
n² + n - 2m ≤ 0
n ≤ (-1 + √(1+8m))/2 ≈ √(2m)

因此枚舉 n 從 floor(√(2m)) 遞減至 2，自然產生**起始數遞增**的序列順序。

完整 C 代碼 (優化版)

#include <stdio.h>
#include <math.h>

int main() {
    long long m;
    if(scanf("%lld", &m) != 1 || m <= 0) return 0;

    int found = 0;
    long long max_n = (sqrt(1 + 8.0*m) - 1) / 2;  // 精確上界

    for(long long n = max_n; n >= 2; n--) {
        // a = m/n - (n-1)/2 必須為整數
        // 等價：2m = n(2a + n - 1) → 2m % n == 0 且 (2m/n - n + 1) 為偶數
        if((2*m) % n != 0) continue;
        
        long long t = (2*m)/n - n + 1;
        if(t <= 0 || (t & 1)) continue;  // t 必須為正偶數
        
        long long a = t / 2;
        if(a < 1) continue;
        
        found = 1;
        for(long long i = 0; i < n; i++) {
            if(i) printf(" ");
            printf("%lld", a + i);
        }
        printf("\n");
    }

    if(!found) printf("NONE\n");
    return 0;
}

關鍵優化點

數學等價轉換證明

a = m/n - (n-1)/2 為整數
⇔ 2a = 2m/n - n + 1 為整數
⇔ 2m/n 為整數 且 (2m/n - n + 1) 為偶數
⇔ n 整除 2m 且 (2m/n - n + 1) % 2 == 0

複雜度分析

• 時間：O(√m) — 枚舉 n 從 √(2m) 到 2
• 空間：O(1) — 僅常數變數
• m=10¹² 時 √m=10⁶，極快

測試驗證

擴展：輸出序列個數統計

序列個數等於 m 的**奇因數個數減 1** (對應 n 為奇數的解) 加上 **2m 的特定偶因數個數**。這關聯到數論中「整數表示為連續整數和的方式數」問題。

總結

連續正整數和分解是「數學建模 → 整數運算優化 → 邊界精確計算」的典型範例。從浮點判斷進化到純整數模運算，從近似上界到精確二次不等式求解，體現了演算法工程化的核心思維：正確性 > 簡潔性 > 效率。