P1147 连续正整数和

May 8, 2026 · 4 分钟阅读 · 模拟数学 ·

文章目录

题目信息

字段	内容
题号	P1147
难度	普及−
知识点	模拟、双指针、等差数列

题目描述

对一个给定的正整数 M，求出所有连续的正整数段（每一段至少有两个数），使得这些连续的正整数之和为 M。

例如：1998 + 1999 + 2000 + 2001 + 2002 = 10000，所以从 1998 到 2002 的一个自然数段为 M = 10000 的一个解。

输入格式

一个正整数 M（10 ≤ M ≤ 2,000,000）

输出格式

每行两个正整数，表示满足条件的连续正整数段的起点和终点，两数之间用一个空格隔开；所有输出行按起点从小到大升序排列；题目保证至少有一个解。

样例

输入

输出

解题思路

核心思想

本题最直接的思路是：枚举序列的起点 i，然后从 i 开始累加，直到和 ≥ M。

具体来说：

枚举起点 i（从 1 到 M）
从 i 开始不断向右扩展终点 j，累加 j 到 sum
当 sum == M 且序列长度 ≥ 2（即 i != j-1）时，输出 i 和 j-1
当 sum > M 时，停止扩展，尝试下一个起点

优化思路（双指针）

上述方法的时间复杂度接近 O(M√M)，对于 M ≤ 2×10⁶ 可以勉强通过。更优的做法是使用双指针（滑动窗口），将时间复杂度降为 O(M)：

维护窗口 [l, r]，以及窗口内所有数的和 sum
若 sum < M，则右移 r，扩大窗口
若 sum > M，则右移 l，缩小窗口
若 sum == M 且窗口长度 ≥ 2，记录答案

完整代码

C++（朴素枚举)

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        int sum = 0;
        int j   = i;
        while (sum < n) {
            sum += j;
            j++;
        }
        // 序列至少有两个数：i != j-1
        if (sum == n && i != j - 1) {
            cout << i << " " << j - 1 << '\n';
        }
    }
    return 0;
}

C++（双指针优化版）

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;
    cin >> m;

    int l   = 1;
    int r   = 1;
    int sum = 0;

    while (l <= m / 2 + 1) {   // 起点最多到 m/2+1
        if (sum < m) {
            sum += r;
            r++;
        } else if (sum > m) {
            sum -= l;
            l++;
        } else {   // sum == m
            if (l != r - 1) {
                cout << l << " " << r - 1 << '\n';
            }
            sum -= l;
            l++;
        }
    }
    return 0;
}

关键代码讲解

朴素枚举版

for (int i = 1; i <= n; i++) {
    int sum = 0;
    int j = i;
    while (sum < n) { sum += j; j++; }
    if (sum == n && i != j - 1) { cout << i << " " << j - 1 << '\n'; }
}

对每个起点 i，从 i 开始累加，直到 sum ≥ n
循环结束时 j 是第一个使 sum ≥ n 的位置（不包含在序列内），所以终点为 j-1
条件 i != j-1 保证序列至少有两个数

双指针优化版

while (l <= m / 2 + 1) {
    if (sum < m)      { sum += r; r++; }
    else if (sum > m) { sum -= l; l++; }
    else               { /* 找到解 */ sum -= l; l++; }
}

sum < m：窗口和太小，右移 r 扩大窗口
sum > m：窗口和太大，右移 l 缩小窗口
sum == m：找到合法序列，输出后右移 l 继续寻找
起点最多枚举到 m/2 + 1，因为再往后序列长度不可能 ≥ 2

复杂度分析

方法	时间复杂度	空间复杂度
朴素枚举	O(M√M)（近似）	O(1)
双指针	O(M)	O(1)

易错点

序列至少有两个数：必须检查 l != r-1（或等价条件），只输出长度 ≥ 2 的序列
终点为 j-1：while 循环退出时 j 已被多增一次，实际序列终点是 j-1
输出按起点升序：朴素枚举天然满足；双指针法也满足（起点 l 单调递增）
M 最大为 2×10⁶：朴素枚举在洛谷上可以 AC，但更推荐双指针优化

其他语言解法

Python

def solve() -> None:
    m: int = int(input())
    l = 1
    r = 1
    s = 0
    while l <= m // 2 + 1:
        if s < m:
            s += r
            r += 1
        elif s > m:
            s -= l
            l += 1
        else:
            if l != r - 1:
                print(l, r - 1)
            s -= l
            l += 1


if __name__ == '__main__':
    solve()

Java

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(br.readLine().trim());

        int l   = 1;
        int r   = 1;
        int sum = 0;

        while (l <= m / 2 + 1) {
            if (sum < m) {
                sum += r;
                r++;
            } else if (sum > m) {
                sum -= l;
                l++;
            } else {
                if (l != r - 1) {
                    System.out.println(l + " " + (r - 1));
                }
                sum -= l;
                l++;
            }
        }
    }
}

Go

package main

import (
    "bufio"
    "fmt"
    "os"
)

func main() {
    in := bufio.NewReader(os.Stdin)
    var m int
    fmt.Fscan(in, &m)

    l   := 1
    r   := 1
    sum := 0

    for l <= m/2+1 {
        if sum < m {
            sum += r
            r++
        } else if sum > m {
            sum -= l
            l++
        } else {
            if l != r-1 {
                fmt.Println(l, r-1)
            }
            sum -= l
            l++
        }
    }
}

JavaScript

'use strict';

function solve(m) {
    let l   = 1;
    let r   = 1;
    let sum = 0;

    while (l <= Math.floor(m / 2) + 1) {
        if (sum < m) {
            sum += r;
            r++;
        } else if (sum > m) {
            sum -= l;
            l++;
        } else {
            if (l !== r - 1) {
                console.log(l + ' ' + (r - 1));
            }
            sum -= l;
            l++;
        }
    }
}

const m = parseInt(require('fs').readFileSync('/dev/stdin', 'utf8').trim(), 10);
solve(m);