猫史档案馆

用户:

大黄鸡走走Code查看:2 回复:3 评论:2 创建时间:2023-12-28T19:47:29

题目描述]

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

输入

一行，包含一个整数为M的值（1<= M <= 2,000,000）

输出

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

求看看这段代码有什么问题，题目在上面

include<bits/stdc++.h> using namespace std; int main() { int m; cin>>m; for(int i=1;i<m/2;i++) { int sum=i,j=i; while(sum<m) { j++; sum+=j; } if(sum==m)cout<<i<<" "<<j<<endl; } }

可爱的呆鲨鱼帝

前缀和，秒了

#include <bits/stdc++.h>
#include<iostream>
using ll=long long;//这里用long long 喵位整数才能满足大数要求。
const ll maxn = 2e6 + 10;
ll sum[maxn];
void search_nlogn(ll n) {
    sum[1] = 1;
    for (int i = 2; i <= n; i++) {
        sum[i] = sum[i - 1] + i;
    }
    for (int i = 0; i <= n; i++) {
        ll x = sum[i];
        ll y = x + n;
        int j = lower_bound(sum, sum + n, y) - sum;
        if (sum[j] == x + n && j > (i + 1)) {//筛掉不符合的数据，保持严谨
            cout << i + 1 << " " << j << endl;
        }
    }
}
int main(){
    ll M;
    cin>>M;
    ll a,b;
    search(M);
    return 0;
}

PlumSteven

楼下那位看上去比较正确（不大确定不用using namespace std; cin还不加std::能不能编译过）

但这道题丝毫不用二分+前缀和（杀鸡焉用牛刀），首先2e6的数据O(n^2)是肯定不过的，立刻把枚举扔进垃圾桶。

O(nlogn)评测器给你卡一卡就过不去了，最稳妥的还是O(n)

这道题怎么用O(n)来解呢？

我们只需要先枚举开头，我们把它叫做k，设数列长度为x，则列方程：(k+k+x-1)x=2m

解得：x=sqrt(2m+(k-0.5)^2)+0.5-k

算一算再判断x是否是整数即可

进一步缩小范围，根据题目，易知开头绝对不会大于等于m/2，就绝对能过了。

SCS_user_EHQ0z2l6el

最明显的，没加#

猫史档案馆

（求助)c++ 麻烦哪位大佬看一下我的代码哪错了

回复