信奥赛-刷题笔记-前缀和篇-T2-P1147连续自然数和0525

原创

IT从业者张某某

修改于 2025-05-26 08:43:55

12500

代码可运行

文章被收录于专栏：信奥赛-刷题笔记信奥赛-刷题笔记

运行总次数：0

代码可运行

总题单

本部分总题单如下

【腾讯文档】副本-CSP-JS+NOI 题单 (未完待续)

https://docs.qq.com/sheet/DSmJuVXR4RUNVWWhW?tab=BB08J2

前缀和篇题单

P1147 连续自然数和

https://www.luogu.com.cn/problem/P1147

题目描述

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

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

输入格式

包含一个整数的单独一行给出 M 的值（10 \le M \le 2,000,000 ）。

输出格式

每行两个正整数，给出一个满足条件的连续正整数段中的第一个数和最后一个数，两数之间用一个空格隔开，所有输出行的第一个按从小到大的升序排列，对于给定的输入数据，保证至少有一个解。

输入输出样例 #1

输入 #1

输出 #1

代码1

前缀和这个会超时

#include<bits/stdc++.h>

using namespace std;
const int a = 2e6+10;
int s[a];

int main(){
	int m;
	cin>>m;
	
	// 连续值 与 前缀和
	for(int i=1;i<=m;i++){
		s[i] = s[i-1]+i;
	}
	
	// 求出连续和为m的
	for(int i=1;i<=m/2;i++){
		for(int j=i+1;j<=m/2+1;j++){
			if(s[j]-s[i-1]==m) cout<<i<<" "<<j<<endl;
		}
	} 
	
	
	return 0;
}

代码2-滑动窗口法

#include <bits/stdc++.h>  // 万能头文件，包含所有标准库函数
using namespace std;

int main() {
    int m;
    cin >> m;  // 输入目标和 M

    int l = 1, r = 1;  // 双指针初始化，表示当前考虑的区间 [l, r)
    int sum = 0;       // 当前区间的和（初始为 0）

    // 主循环，直到左指针超过 m/2 为止
    // 因为如果起始点大于 m/2，那么两个数之和一定大于 m
    while (l <= m / 2) {

        // 当前和小于目标值，扩大右边界
        if (sum < m) {
            sum += r;  // 把当前 r 加入和中
            r++;       // 右指针向右移动
        }

        // 当前和大于目标值，缩小左边界
        else if (sum > m) {
            sum -= l;  // 去掉最左边的数
            l++;       // 左指针向右移动
        }

        // 找到一组解
        else {
            // 输出当前区间 [l, r-1]
            cout << l << " " << r - 1 << endl;

            // 移动左指针，尝试下一种可能
            sum -= l;
            l++;
        }
    }

    return 0;
}

✅ 滑动窗口法思路简述：

使用两个指针 l 和 r 表示当前考虑的连续自然数段的起点和终点。
维护一个变量 sum 表示 [l, r) 区间内的数字之和（即从 l 到 r-1 的和）。
根据 sum 和 m 的大小关系移动指针：
- 如果 sum < m：扩大右边界，增加 sum
- 如果 sum > m：缩小左边界，减少 sum
- 如果 sum == m：找到一组解，输出结果

🔍 示例解析（以 `m = 15` 为例）

我们手动模拟一下这个过程：

步骤	l	r	sum	状态
1	1	1	0	sum < 15 → 加 r
2	1	2	1	sum < 15 → 加 r
3	1	3	3	sum < 15 → 加 r
4	1	4	6	sum < 15 → 加 r
5	1	5	10	sum < 15 → 加 r
6	1	6	15	sum == 15 → 输出 1,5
7	2	6	14	sum < 15 → 加 r
8	2	7	14+6=20	sum > 15 → 减 l
9	3	7	18	sum > 15 → 减 l
10	4	7	15	sum == 15 → 输出 4,6
...	...	...	...	...

最终输出：

1 5
4 6

验证：

1+2+3+4+5 = 15
4+5+6 = 15

⚙️ 时间复杂度分析

每个指针最多移动 m/2 次
所以总时间复杂度是：O(M)

这比暴力双重循环的 O(M²) 快得多！

代码3

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

int main(){
    cin >> m;

    // 枚举可能的连续数个数 k1（从最大可能值开始）
    for(int k1 = sqrt(2 * m); k1 > 1; k1--) {
        // 判断 (2*m)/k1 是否是整数，并且 k1 和 (2m/k1) 一奇一偶
        if (2 * m % k1 == 0 && (k1 + 2 * m / k1) % 2 == 1) {
            int k2 = 2 * m / k1;

            // 计算起始数 a 和结束数 b
            int a = (k2 - k1 + 1) / 2;
            int b = (k1 + k2 - 1) / 2;

            cout << a << " " << b << endl;
        }
    }

    return 0;
}

这段代码的目的是找出所有满足和为给定正整数 M 的连续自然数段。下面我将详细解释这段代码的逻辑。

问题分析

我们需要找出所有连续的自然数序列，使得它们的和等于 M。例如：

对于 M = 10000，其中一个解是：

1998 + 1999 + 2000 + 2001 + 2002 = 10000

所以输出是：

1998 2002

数学推导

我们设一个连续自然数段的起始数为 a，长度为 n，那么这个序列就是：

a, a+1, a+2, ..., a+n-1

它的和是等差数列求和公式：

\text{sum} = \frac{n}{2}(2a + n - 1)

我们要让它等于 M，即：

\frac{n}{2}(2a + n - 1) = M

两边乘以 2 得到：

n(2a + n - 1) = 2M ·`

我们可以枚举 n（也就是连续数的个数），然后看看是否存在整数 a 满足这个式子。

整理一下：

2a = \frac{2M}{n} - n + 1 \Rightarrow a = \frac{\frac{2M}{n} - n + 1}{2}

所以只要 \frac{2M}{n} - n + 1 是偶数，并且结果大于 0，就说明存在一个合法的起始数 a。

代码详解

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

int main(){
    cin >> m;

    // 枚举可能的连续数个数 k1（从最大可能值开始）
    for(int k1 = sqrt(2 * m); k1 > 1; k1--) {
        // 判断 (2*m)/k1 是否是整数，并且 k1 和 (2m/k1) 一奇一偶
        if (2 * m % k1 == 0 && (k1 + 2 * m / k1) % 2 == 1) {
            int k2 = 2 * m / k1;

            // 计算起始数 a 和结束数 b
            int a = (k2 - k1 + 1) / 2;
            int b = (k1 + k2 - 1) / 2;

            cout << a << " " << b << endl;
        }
    }

    return 0;
}

逐行解释

输入部分

cin >> m;

读入目标和 m。

循环部分

for(int k1 = sqrt(2 * m); k1 > 1; k1--)

这里 k1 表示的是连续自然数的个数 n。我们知道最大可能的 n 是当数列是从 1 开始的等差数列时：

1 + 2 + ... + n = \frac{n(n+1)}{2} \leq M \Rightarrow n^2 + n \leq 2M \Rightarrow n \approx \sqrt{2M}

所以我们从 sqrt(2*M) 开始往下枚举连续自然数个数 n（也就是 k1）。

判断条件

if (2 * m % k1 == 0 && (k1 + 2 * m / k1) % 2 == 1)

2*m % k1 == 0：确保 2m/k1 是整数（因为后面要用它来计算 a）。
(k1 + 2*m/k1) % 2 == 1：确保 k1 和 2m/k1 一奇一偶，这样可以保证 (k2 - k1 + 1) 是偶数，从而 a 是整数。

计算起始点和终点

int k2 = 2 * m / k1;
int a = (k2 - k1 + 1) / 2;
int b = (k1 + k2 - 1) / 2;

a 是起始数；
b 是终止数；
这两个公式来自前面的数学推导。

输出结果

cout << a << " " << b << endl;

输出每组符合条件的连续自然数段的起始和终止数。

排序输出的原理

虽然我们在倒序枚举 k1（连续数个数），但最终输出的却是按起始数从小到大排列的。这是因为在满足条件的情况下，较小的 a 对应较大的 k1，所以先输出的其实是小的起始数。

总结

该算法利用了数学推导，将暴力枚举优化到了 $O(\sqrt{M})$ 时间复杂度，非常高效。它通过枚举连续自然数的个数 n，快速判断是否存在对应的起始数 a，并输出所有符合条件的区间。

样例运行

对于输入：

输出：

这表示有四组连续自然数加起来等于 10000：

18 到 142
297 到 328
388 到 412
1998 到 2002

希望这个解释对你理解这段代码有所帮助！如果你还想了解其他实现方式或更详细的数学推导，也可以继续问我 😊

现场真题注意事项

https://cspoj.com/contest.php?cid=1002Fus5yz4x3EcSJH1Z

注意事项

文件名（程序名和输入输出文件名）必须使用英文小写。（提交必须使用freopen()进行提交）

C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是0。

提交的程序代码文件的放置位置请参考各省的具体要求。

因违反以上三点而出现的错误或问题，申述时一律不予受理。

若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。

程序可使用的栈空间内存限制与题目的内存限制一致。

全国统一评测时采用的机器配置为：Inter® Core™ i7-8700K CPU @3.70GHz，内存 32GB。上述时限以此配置为准。

只提供 Linux 格式附加样例文件。

评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以此为准

假设输入样例数据存在文件test.in中，输出样例数据存在文件test.out中，

则在CSP、NOI等比赛的代码中，需添加freopen、fclose语句，

内容详见模板代码如下。

#include <bits/stdc++.h>
#include<cstdio>//必须包含cstdio头文件
#include<iostream>
using namespace std;
 
int main(){
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	
	cout<<"Hello NOI"<<endl;
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}

复制

下面为函数的简介，详细可参见 http://www.cplusplus.com/reference/clibrary/cstdio/freopen.html

函数名：freopen

声明：

FILE _freopen( const char_ path, const char _mode, FILE_ stream );

所在文件： stdio.h

参数说明：

path: 文件名，用于存储输入输出的自定义文件名。

mode: 文件打开的模式。和fopen中的模式（如r-只读, w-写）相同。

stream: 一个文件，通常使用标准流文件。

返回值：成功，则返回一个path所指定文件的指针；失败，返回NULL。（一般可以不使用它的返回值）

功能：实现重定向，把预定义的标准流文件定向到由path指定的文件中。标准流文件具体是指stdin、stdout和stderr。其中stdin是标准输入流，默认为键盘；stdout是标准输出流，默认为屏幕；stderr是标准错误流，一般把屏幕设为默认。通过调用freopen，就可以修改标准流文件的默认值，实现重定向。

#include<iostream>
#include<cstdio>
using namespace std;
int main(){
    freopen("7532.in", "r", stdin);
    freopen("7532.out", "w", stdout);
    //原来的代码保持不变
    double a, b, r;
    int k;
    cin >> a >> b;
    k = int(a/b);
    r = a - b * k;
    printf("%g", r);
    //-------------
    fclose(stdin);
    fclose(stdout);
    return 0;
}

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯技术创作特训营S13

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯技术创作特训营S13

登录后参与评论

0 条评论

热度