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++;