上海计算机学会2020年11月月赛C++丙组T4连续拆分
发布时间
阅读量：
阅读量
连续拆分
内存限制: 256 Mb时间限制: 1000 ms
题目描述
我们希望将一个正整数 n 拆分成若干个连续的正整数的和，例如 n=18 时：
18=3+4+5+6
就是一种拆分方法。给定一个正整数 n，请找出所有的连续整数拆分方法，注意一种合法的拆分至少需要两项连续的整数。
输入格式
单个整数：表示正整数 n。
输出格式
- 若不存在任何拆分方案，输出
None。 - 若有多个拆分方案，不同方案用换行隔开，先输出项数多的拆分方案。
- 每个拆分方案，应输出一个从小到大的连续正整数序列，每个数字之间用空格隔开。
数据范围
- 对于 30% 的数据，1≤n≤100
- 对于 60% 的数据，1≤n≤10^4。
- 对于 100% 的数据，1≤n≤10^7。
样例数据
输入:
15输出:
1 2 3 4 5
4 5 6
7 8
输入:
4
输出:
None
解析：
连续拆分后的首项a，末项b，则（a+b）（b-a+1）==n，整理一下得到 bb+b=2n+aa-a，可以通过枚举a，计算b，然后打印结果，详见代码：
提示1：数据类型要用long long ，i*i可能会超int。
提示2：若b*b+b==x，则b=sqrt（x）。只是需要反向验证一下。
#include<bits/stdc++.h>
using namespace std;
long long n;
bool flag=1;
int main() {
cin>>n;
for(long long i=1;i<=n/2;i++){
long long x=n*2+i*i-i;
long long b=sqrt(x);
if (b*b+b==x){
for(int j=i;j<=b;j++){
cout<<j<<" ";
}
cout<<endl;
flag=0;
}
}
if (flag==1){
cout<<"None";
}
return 0;
}
AI写代码cpp
全部评论 (0)
还没有任何评论哟~