洛谷 P1147 连续自然数和

题目描述

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

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

输入输出格式

输入格式:

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

输出格式:

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

输入输出样例

输入样例#1: 复制

10000

输出样例#1: 复制

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;
        }
    }
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

6 + 17 =