题目描述
一个正整数一般可以分为几个互不相同的自然数的和，如3=1+2，4=1+3，5＝1+4=2+3，6=1+5＝2+4，…。
现在你的任务是将指定的正整数n分解成m个(m>=1)互不相同的自然数的和，且使这些自然数的乘积最大。
输入
只一个正整数n，(3≤n≤10000)。
输出
第一行是分解方案，相邻的数之间用一个空格分开，并且按由小到大的顺序。
第二行是最大的乘积。
样例输入
10
样例输出
2 3 5
30
数据范围限制
30%的数据 3<=n<=100
程序
#include<cstdio>
#include<iostream>
using namespace std;
int n,m,l,w,k[10001],a[10000],maxn=10000;
void gaojin(int x)
{
int g=0,k=0;
for (int i=maxn;i>=1;i--)
{
g=a[i]*x+k;
a[i]=g%10;
k=g/10;
}
}
int main()
{
freopen("max.in","r",stdin);
freopen("max.out","w",stdout);
cin>>n;
m=n;
l=2;
if (n==4)
{
cout<<n<<endl;
cout<<n;
return 0;
}
while (m>=l)
{
w++;
k[w]=l;
m-=l;
l++;
}
if (m<=w) for (int i=m;i>=1;i--) k[w-i+1]++;
else
{
for (int i=w;i>=1;i--) k[w-i+1]++;
for (int i=m-w;i>=1;i--) k[w-i+1]++;
}
a[maxn]=1;
for (int i=1;i<=w;i++)
{
cout<<k[i]<<' ';
gaojin(k[i]);
}
cout<<endl;
l=1;
while (a[l]==0) l++;
for (int i=l;i<=maxn;i++)
cout<<a[i];
fclose(stdin);
fclose(stdout);
return 0;
}