蓝桥杯备考-----》前缀和+哈希表之连续自然数和
M是2e6级别的，我们如果N平方必然是过不了滴
当然，我们枚举的时候并不需要枚举那么多，
我们只需要枚举M的一半儿就行了
我们用前缀和，提前把0下标标记为0 ，如果f[i]刚好是sum的话，就输出1到i
如果f[i]不是sum的话，我们用mp寻找一下有没有 f[i]-sum 的数，如果有的话，我们输出mp[f[i]-sum]+1到i
好的，我们来实现一下代码
#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long ll;
unordered_map <ll,int> mp;
ll sum;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll m;cin >> m;
mp[0]=0;
for(int i = 1;i<=m/2+1;i++)
{
sum+=i;
if(mp.count(sum-m))
{
cout << mp[sum-m] +1 << " " <<i << endl;
}
mp[sum]=i;
}
}