HDU 2058 The sum problem：數學推導求連續區間和

問題描述

求 [1,n] 中連續子區間，使元素和為 m。輸出所有滿足條件的區間 [L,R]。多測試用例，以 0 0 結束。

數學公式

區間 [i, j] 和 = (i+j)*(j-i+1)/2 = m。
設長度 k = j-i+1，首項 i。則 (2i+k-1)*k = 2m。
枚舉 k 從 √(2m) 遞減至 1，解 i = (2m/k - k + 1)/2。若 i 為正整數且 i+k-1 ≤ n，則為有效區間。

代碼實現

int main() {
    int n,m;
    while (scanf("%d%d",&n,&m), n||m) {
        for (int k=(int)sqrt(2*m); k>=1; k--) {
            int i = (2*m/k - k + 1)/2;
            if ((2*i+k-1)*k == 2*m && i+k-1 <= n)
                printf("[%d,%d]\n", i, i+k-1);
        }
        printf("\n");
    }
    return 0;
}

關鍵點

• 枚舉長度 k 而非起點，利用 k ≤ √(2m) 縮小範圍。
• 整除檢查 (2*i+k-1)*k == 2*m 避免浮點誤差。
• 按 k 遞減枚舉，輸出區間長度從大到小（符合樣例順序）。

總結

HDU 2058 是純數學題。關鍵在於將連續區間和轉化為關於長度 k 的方程，並利用 k ≤ √(2m) 的性質高效枚舉。代碼極短，數學推導優美。