正整數表示為連續整數和的判定條件與算法實現

探討正整數 n 能否表示為 k+1 個連續正整數之和（k ≥ 1），推導數學條件並給出 C++ 實現代碼。

數學模型

設連續整數為 a, a+1, ..., a+k，和為：

n = (a + a + k) * (k + 1) / 2 = (2a + k)(k + 1) / 2

解得：

a = n/(k+1) - k/2

條件：a 為正整數，即 a > 0 且 a 為整數。

算法設計

• k 最大值由 a ≥ 1 推導：(k+1)(k+2)/2 ≤ n → k ≤ √(2n)
• 從大到小枚舉 k，優先輸出項數最多的分解
• 計算 a，判斷是否為正整數

C++ 實現 (G++ 編譯)

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n;
    cout << "input n: " << endl;
    cin >> n;
    
    int maxk = (int)sqrt(2.0 * n);
    bool found = false;
    
    for (int k = maxk; k >= 1; --k) {
        double a = n / double(k + 1) - k / 2.0;
        if (a > 0 && a == (int)a) {
            for (int j = 0; j <= k; ++j) {
                cout << (int)a + j << " ";
            }
            cout << endl;
            found = true;
        }
    }
    
    if (!found) cout << "NONE" << endl;
    return 0;
}

測試示例

input n: 15
7 8
4 5 6
1 2 3 4 5

input n: 8
NONE

相關資源

• 等差數列求和推導：CSDN 博客
• 教學示例：NTU 課程