输入 m，输出所有满足 l+(l+1)+(l+2)+\cdots+(r-2)+(r-1)+r=m 的 l 和 r。
按 l 从小到大的排列输出。
思路详解
O(m^3) 算法（10 分）
不难想到我们可以暴力枚举 l 和 r，判断 l \sim r 之间所有整数的和是不是 m。
#include<iostream>
#define ll long long
using namespace std;
ll m; //2e6的规模，不开 long long 见祖宗
int main(){
cin >> m;
for(ll l = 1;l<m;l++){ //枚举左边界
for(ll r = l+1;r<=m;r++){ //枚举右边界
ll sum=0; //求 l~r 之间所有数的和
for(ll i = l;i<=r;i++){
sum+=i; //累加
}
if(sum==m){ //判断和是否等于 m
cout << l << " " << r << endl; //如果相等，输出 l 和 r
}
}
}
return 0;
}
显然，这个代码对于 2 \times 10^{6} 的规模会严重超时。
O(m^2) 算法（10+15 分）
求 l \sim r 之间的所有整数的和是多少，不难发现是等差数列，因此直接用等差数列求和公式即可。
#include<iostream>
#define ll long long
using namespace std;
ll m; //2e6的规模，不开 long long 见祖宗
int main(){
cin >> m;
for(ll l = 1;l<m;l++){ //枚举左边界
for(ll r = l+1;r<=m;r++){ //枚举右边界
ll sum=(l+r)*(r-l+1)/2; //套用求和公式
if(sum==m){ //判断和是否等于 m
cout << l << " " << r << endl; //如果相等，输出 l 和 r
}
}
}
return 0;
}
显然，这个代码对于 2 \times 10^{6} 的规模还是会严重超时。
但是由于学校OJ数据太水了，这个代码也能卡过去。所以我帮学校造了几组数据。
测试点 3 \sim 5 能卡掉你的代码。
O(m \log m) 算法（10+15+20 分）
如果我们已经确定左边界 l，想求一个右边界 r，满足 l \sim r 之间所有整数的和为 m，不难想到二分。
#include<iostream>
#define ll long long
using namespace std;
ll m; //2e6的规模，不开 long long 见祖宗
int main(){
cin >> m;
for(ll l = 1;l<m;l++){ //枚举左边界
int x=l+1,y=m; //x 和 y 就是枚举 r 的左右边界
while(x<=y){
ll r=(x+y)/2; //二分取中间
ll sum=(l+r)*(r-l+1)/2; //套用求和公式
if(sum==m){ //判断和是否等于 m
cout << l << " " << r << endl; //如果相等，输出 l 和 r
break; //记得退出循环，不然就会进入死循环
}
else if(sum<m){
x=r+1; //如果 r 太小了，就要把 r 的范围调大，因此要把 x 调大
}
else{
y=r-1; //如果 r 太大了，就要把 r 的范围调小，因此要把 y 调小
}
}
}
return 0;
}