洛谷 P1147 连续自然数和题解

P1147 连续自然数和

题目描述

对一个给定的自然数MM，求出所有的连续的自然数段，这些连续的自然数段中的全部数之和为MM。

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

输入格式

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

输出格式

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

输入输出样例

输入 #1

10000

输出 #1

18 142

297 328

388 412

1998 2002

【思路】

暴力、枚举

很有意思的一道题目，看着很简单，会往最简单最暴力的方法上去想

但是数据很容易让人心生胆怯，然后就不敢用，只能绞尽脑汁去想着怎么优化怎么减少复杂度

我就在这么一道明明很简单的题目上，

想优秀的解法上面耗费了大量的时间

但是殊不知，最最暴力的方法确实最最可行的方法

直接暴力枚举1 - n/2个数然后枚举每一个数是否有可行的区间就可以了

这里说一下为什么要枚举到n/2而不是 n

拿样例举个例子吧

因为这题中连续的区间虽然没有明说但是从数据里面可以推断出，

区间长度必须是大于1，因为样例的输出里面没有本身10000 - 10000这个区间

所以至少一个区间是有2个数的，

而2个数可以拼出10000的应该是比10000 / 2的值小或者等于的，

因为如果大于n / 2那是不可能有两个连续的数拼出n的，不信你可以自己试试（滑稽）

所以说只需要枚举到n / 2就可以了

代码里面有一个小细节用注释标注出来了

#include<iostream>

#include<cstdio>

using namespace std;

int main()

{

	int n;

	cin >> n;

	int qwq = n / 2;

	int sum = 0;

	for(int i = 1;i <= qwq;++ i)

	{

		sum = 0;

		int j;

		for(j = i;j <= n;++ j)//解释一下这里为什么是n

		//如果输入的数据是偶数的话，那是不会有任何毛病的

		//但是如果你输入的是奇数，拿1919来举例的

		//这个1919 / 2之后等于959.5，这个刚好是有一个可行区间为959 - 960的也就是将两个959.5分配了一下凑出来两个相邻的整数

		//这样如果只枚举到n / 2就是jj掉

		{

			sum += j;

			if(sum >= n)

				break;

		}

		if(sum == n)cout << i << " " << j << endl;

	}

	return 0;

}

巴特西

洛谷 P1147 连续自然数和题解

P1147 连续自然数和

题目描述

输入格式

输出格式

输入输出样例

【思路】

最新文章

热门文章

巴特西

洛谷 P1147 连续自然数和 题解

P1147 连续自然数和

题目描述

输入格式

输出格式

输入输出样例

【思路】

最新文章

热门文章

洛谷 P1147 连续自然数和题解