洛谷 P1147 连续自然数和

题目描述

对一个给定的自然数 $M$ ，求出所有的连续的自然数段，这些连续的自然数段中的全部数之和为 $M$ 。

例子： $1998+1999+2000+2001+2002=10000$ ，所以从 $1998$ 到 $2002$ 的一个自然数段为 $M=10000$ 的一个解。

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

10000

18 142 
297 328 
388 412 
1998 2002

1.暴力解法：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,sum,j;
int main()
{
    cin>>n;     //读入       
    for(int i=1;i<=n/2;i++)
    {
        sum=0;     //sum归零
        for(j=i;j<n;j++)   //枚举每一个i对应的j，这个j是最小的，从i加到j总和大于等于n的自然数
        {
            sum+=j;            //sum记录从i加到j的总和
            if(sum>=n)break;    //当sum>=n时，跳出循环
        }
        if(sum==n)cout<<i<<' '<<j<<endl;   //输出
    }
    return 0;
}

本题可以通过等差数列求和，解一元二次方程得出答案。设首项是i,末项是x，和为n,则

(i+x)(x-i+1)/2=n (等差数列求和)
(i+x)(x-i+1)=2n
ix-i^2+i+x^2-ix+x=2n  (多项式乘多项式)
x^2+x-i^2+i-2n=0  (合并同类项)

运用一元二次方程求根公式，得

x1=(-1-sqrt(1-4(i-i^2-2n)))/2×2=(-1+sqrt(1-4(i-i^2-2n)))/2

我们在这里就只要保留x2就可以了，应为x1必定小于i如果x2是整数且大于i，那么它就符合了题目要求。我们只要枚举i就可以得到结果。

#include<cmath>
#include<iostream>
using namespace std;
int main()
{
    int n;
    long long y;
    long double x;
    cin>>n;
    for (int i=1;i<n;i++)
    {
        y=i;  
        //注意，一定要先把i保存到y里，不然下面在运行i*i是，结果是暂存在i里的，数据大了就会炸（我就因为这个原因改了2个小时）
        if (1-4*(y-y*y-2*n)>=1)  
        //根的判别式(我们要满足(-1+sqrt(1-4(i-i^2-2n)))是正数)
        {
            y=1-4*(y-y*y-2*n);
            x=(-1+sqrt(y))/2;  //求此方程的解
            if ((x==floor(x))and(x>i))  
            //判断此方程的根是否为正数且大于i cout<<i<<" "<<floor(x)<<endl;
        }
    }
}