洛谷的刷题日常之P1147

连续自然数和

• 描述：

对一个给定的自然数$M$，求出所有的连续的自然数段，这些连续的自然数段中的全部数之和为$M$。
例子：1998+1999+2000+2001+2002 = 10000，所以从1998到2002的一个自然数段为$M=10000$的一个解。

• 输入：

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

• 输出：

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

• 输入样例：

10000

• 输出样例：

18 142
297 328
388 412
1998 2002

• 解题思路：前缀和+二分

• 参考代码:

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

#define ll long long
ll sum[2000010];

int main() {
    ll m;
    scanf("%lld",&m);
    for(int i=1;i<=m;i++)  sum[i]=sum[i-1]+i;
    for(int i=1;i<=m-1;i++) {
        ll l=i,r=m-1,mid;
        while(l<=r) {
            mid=(l+r)/2;
            ll t=sum[mid]-sum[i-1];
            if(t==m) {
                printf("%d %d\n",i,mid);
                break;
            }else if(t<m) {
                l=mid+1;
            }else {
                r=mid-1;
            }
        }
    }
    return 0;
}