HDU 2058: The Sum Problem - 連續序列求和數學解法

問題描述

給定 n, m，在小於 n 的正整數中，找出所有連續序列使其和等於 m，按起始數從小到大輸出區間 [a, b]。多組數據，n=m=0 結束。

數學推導

設連續序列長度為 L，起始數為 a，則和為 L*a + L*(L-1)/2 = m。移項得 a = (m - L*(L-1)/2) / L。要求 a 為正整數，即分子能被 L 整除且結果 > 0。

枚舉 L 從 1 開始，直到 m - L*(L-1)/2 <= 0。若整除，計算 a, b=a+L-1，存入棧中（因 L 遞增，a 遞減，用棧反序輸出滿足起始數從小到大）。

代碼要點

用 stack 暫存合法區間，枚舉結束後彈出輸出。注意 n > m 時可令 n = m（因序列數均 < n，和為 m，最大數不超過 m）。

完整代碼

#include <bits/stdc++.h>
using namespace std;

struct Node { int a, b; };

int main() {
    int n, m;
    while (cin >> n >> m, n || m) {
        if (n > m) n = m;
        stack<Node> st;
        for (int L = 1; ; ++L) {
            int numerator = m - L*(L-1)/2;
            if (numerator <= 0) break;
            if (numerator % L == 0) {
                int a = numerator / L;
                if (a < n) st.push({a, a+L-1});
            }
        }
        while (!st.empty()) {
            auto nd = st.top(); st.pop();
            cout << '[' << nd.a << ',' << nd.b << ']' << endl;
        }
    }
    return 0;
}