洛谷P1147连续自然数和

采用前缀和思想，用二分查找寻找区间，时间复杂度O(n+nlogn)

#include<bits/stdc++.h>
#define maxn 2000000
using namespace std;
long long arr[maxn+1];
long long brr[maxn+1];
int main()
{
	brr[0]=0;
	for(int i=1;i<=maxn;i++)
	{
		arr[i]=i;
		brr[i]=brr[i-1]+arr[i];
	}
	int m;cin>>m;
	for(int i=1;i<=maxn;i++)
	{
		int pos=lower_bound(brr+1,brr+maxn+1,brr[i]+m)-brr;
		if(brr[pos]-brr[i]==m&&pos!=i+1)cout<<i+1<<" "<<pos<<endl;
	}
	return 0;
}