题目描述
对一个给定的自然数 ,求出所有的连续的自然数段,这些连续的自然数段中的全部数之和为 。
例子: 1998+1999+2000+2001+2002 = 10000 ,所以从 1998 到 2002 的一个自然数段为 M=10000 的一个解。
输入输出格式
输入格式:
包含一个整数的单独一行给出M的值( 10 \le M \le 2,000,000 )。
输出格式:
每行两个自然数,给出一个满足条件的连续自然数段中的第一个数和最后一个数,两数之间用一个空格隔开,所有输出行的第一个按从小到大的升序排列,对于给定的输入数据,保证至少有一个解。
输入输出样例
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)))/2x2=(-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; } } }