天天看点

P1147 连续自然数和洛谷

P1147 连续自然数和洛谷

题目链接:

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

题目描述

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

例子:

1998+1999+2000+2001+2002=10000,

所以从1998到2002的一个自然数段为M=10000的一个解。

输入格式

包含一个整数的单独一行给出M的值

(10<=M <=2,000,000)。

输出格式

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

输入输出样例

输入

10000

输出

18 142

297 328

388 412

1998 2002

#include<bits/stdc++.h>
using namespace std;
int main(){
	int ans[2000006];//用来存储前多少项和
	int m;
	scanf("%d",&m);
	ans[0]=0;
	for(int i=1;i<=m+6;i++){
		ans[i]=i+ans[i-1];//ans[i]储存前i项数和
	}
	int l=0,r=1;//最小情况
	while(1){//利用死循环进行运算
		if(ans[r]-ans[l]>m){
			l++;
		}//l+1项到r项和
		if(ans[r]-ans[l]==m){
			printf("%d %d\n",l+1,r);
			//l加一不能漏掉 
			l++;
			//继续寻找下一个符合要求的区间 
			r++;
		}
		if(ans[r]-ans[l]<m){
			r++;
		}
		if(r>m/2+2){
		//注意写退出条件 +2是为了保险起见 
		//当r>m时,区间和必大于m
			break;
		} 
	}
	return 0;
}
           

注:本题在进行二分查找区间时候赋值l=0,r=1;

这是最初始区间,r与l都为最小,

因此我们在寻找ans[r]-ans[l]的差值=m的区间(或区间个数)时,

只能先通过判断情况再r++或者l++来改变差值,

符合情况时r++且l++;

继续阅读