【GESP】C++五级/四级练习（双指针/数学） luogu-P1147 连续自然数和
GESP C++ 五级(四级)练习题，双指针（尺取法）和数学计算考点。题目难度⭐⭐★☆☆，适合练习对连续区间和的控制。洛谷难度等级普及−
luogu-P1147 连续自然数和
题目要求
题目描述
对一个给定的正整数 $M$，求出所有的连续的正整数段（每一段至少有两个数），这些连续的自然数段中的全部数之和为 $M$。
例子：$1998+1999+2000+2001+2002 = 10000$，所以从 $1998$ 到 $2002$ 的一个自然数段为 $M=10000$ 的一个解。
输入格式
包含一个整数的单独一行给出 $M$ 的值（$10 \le M \le 2,000,000$）。
输出格式
每行两个正整数，给出一个满足条件的连续正整数段中的第一个数和最后一个数，两数之间用一个空格隔开，所有输出行的第一个按从小到大的升序排列，对于给定的输入数据，保证至少有一个解。
输入输出样例 #1
输入 #1
1
10000
输出 #1
1
2
3
4
18 142
297 328
388 412
1998 2002
题目分析
题目要求找出和为 $M$ 的连续正整数序列。设序列为 $i, i+1, \dots, j$。
方法一：双指针法（尺取法）
这是一个经典的可以用双指针（Sliding Window）解决的问题。 我们维护一个区间 $[l, r]$，以及这个区间内所有数字的和 sum。 初始时，从最小的区间 $l=1, r=2$ 开始，sum = 3。
- 如果 sum < M：说明当前的和还不够大，我们需要让区间右端点 $r$ 向右移动（扩大窗口），并加上新的 $r$ 值。
- 如果 sum > M：说明当前的和太大了，我们需要让区间左端点 $l$ 向右移动（缩小窗口），并减去旧的 $l$ 值。
- 如果 sum == M：找到了一个满足条件的区间！输出 $l$ 和 $r$。然后我们可以让 $l$ 继续向右移动，尝试寻找下一个可能的区间（因为题目要求输出所有解）。
循环终止条件：当 $l$ 超过 $M/2$ 时即可停止（因为至少两个数，最大的数大概就在 $M/2$ 附近，再往后单个数都接近或超过 $M$ 了，不可能构成和为 $M$ 的序列）。
方法二：数学公式法
根据等差数列求和公式，长度为 $k$ 的连续自然数段（首项为 $a$）的和为： \(S = \frac{k(2a + k - 1)}{2} = M\) 整理得： \(k(2a + k - 1) = 2M\) \(2a = \frac{2M}{k} - k + 1\) \(a = \frac{M}{k} - \frac{k-1}{2}\)
由于 $a$ 必须是正整数：
- 我们可以枚举长度 $k$。$k$ 的范围大致是从 $2$ 开始，直到 $k$ 很大导致 $a \le 0$。
- 粗略估算，$k \approx \sqrt{2M}$。我们可以从 $\sqrt{2M}$ 往下枚举到 $2$。
为什么是从大到小枚举 k？ 题目要求输出时，第一个数 $a$ 按从小到大排列。在和 $M$ 固定的情况下，序列长度 $k$ 越长，起始数字 $a$ 就越小。因此，我们优先枚举最大的 $k$，就能最先找到最小的 $a$，从而直接满足输出顺序要求。
示例代码
方法一、双指针法（推荐）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
int main() {
int m;
std::cin >> m;
// 双指针初始化
// l: 区间左端点
// r: 区间右端点
// sum: 当前区间 [l, r] 的和
int l = 1, r = 2;
long long sum = 3; // 1 + 2 = 3
// 循环条件：左端点小于中点即可，因为至少两个数
// 实际上 l < r 也可以作为条件
while (l <= m / 2) {
if (sum == m) {
// 找到一组解，输出
std::cout << l << " " << r << std::endl;
// 寻找下一组解，左端点右移
sum -= l;
l++;
} else if (sum < m) {
// 和太小，右端点右移，增加 sum
r++;
sum += r;
} else {
// 和太大，左端点右移，减少 sum
sum -= l;
l++;
}
}
return 0;
}
另一种写法是，利用等差数列公式计算sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
int main() {
int M;
std::cin >> M; // 读取目标和 M
int l = 1, r = 2; // 初始化左指针 l 和右指针 r，表示当前连续子段的起点和终点
// (l + r) * (r - l + 1) / 2 是等差数列求和公式，用于计算从 l 到 r 的连续整数和
// 初始 sum 不需赋值，在循环内部计算
long long current_sum = 0; // 使用 long long 避免 sum 溢出
while (l <= (M + 1) / 2) { // 循环条件：左端点 l 理论上不会超过 (M+1)/2，因为至少有2个数，如果 l 超过 M/2，最小的两个数之和就可能超过 M 了
current_sum = (long long)(l + r) * (r - l + 1) / 2; // 计算当前 [l, r] 区间的和
if (current_sum == M) {
// 如果当前区间和等于 M，找到一组解
std::cout << l << " " << r << std::endl;
l++; // 左指针右移，寻找下一个可能的解
} else if (current_sum < M) {
// 如果当前区间和小于 M，说明需要更大的和，右指针右移扩大区间
r++;
} else { // current_sum > M
// 如果当前区间和大于 M，说明和太大，左指针右移缩小区间
l++;
}
}
return 0;
}
方法二、数学法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cmath>
int main() {
int m;
std::cin >> m;
// 根据公式推导，k 的最大值约为 sqrt(2*M)
// 为了让首项 a 从小到大输出，我们需要让 k 从大到小枚举
for (int k = sqrt(2 * m); k >= 2; --k) {
// 判断是否构成整数解
// 2M = k * (2a + k - 1)
// 所以 2M 必须能被 k 整除
long long double_m = 2LL * m;
if (double_m % k == 0) {
long long val = double_m / k;
// val = 2a + k - 1
// 2a = val - k + 1
long long two_a = val - k + 1;
// 2a 必须是偶数，且 a 必须大于 0
if (two_a % 2 == 0 && two_a > 0) {
int a = two_a / 2;
std::cout << a << " " << a + k - 1 << std::endl;
}
}
}
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
