题解：P1147 连续自然数和

CSP_SAKME · 2024-10-04 09:28:47 · 题解

这里提供一种纯二分查找的做法。

思路

利用二分，枚举右端点，利用等差数列求和公式判断是不是一个解，如果是，输出并退出二分。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    for(long long i=1;i<=n;i++){//枚举左端点
        int l=i,r=n+1;//注意边界！
        while(l+1<r){//注意条件！
            long long mid=(l+r)>>1;//等价于(l+r)/2
            long long sum=(i+mid)*(mid-i+1)/2;//等差数列求和公式
            if(sum==n){//如果找到了，输出并退出循环
                cout << i << " " << mid << endl;
                break;
            }else if(sum>n){//大了，就向左查找
                r=mid;
            }else{//否则就是小了，向右查找
                l=mid;
            }
        }
    }
    return 0;
}