题目描述

Description

从文件中读入一个正整n（10≤n≤31000）。要求将n写成若干个正整数之和，并且使这些正整数的乘积最大。 例如，n=13，则当n表示为4+3+3+3（或2+2+3+3+3）时，乘积=108为最大。

Input

只有一个正整数： n （10≤n≤31000）

Output

第1行输出一个整数，为最大乘积的位数。 第2行输出最大乘积的前100位，如果不足100位，则按实际位数输出最大乘积。 （提示：在给定的范围内，最大乘积的位数不超过5000位）。

Sample Input

13

Sample Output

3
108

题目分析

一个正整数n可以分解为和 很显然当n大于4时分解的情况更优
我们来讨论一下n<=4的情况 尽可能不分解出1 因为对乘积没有贡献
当n=3||2时 选择不分解更优
当n=4时 分解成两个2或者不分解都一样
并且选3更优 因为3*3>2*2*2
所以尽可能分解出3 当n%3==1 将一个3和剩余的1变成两个2
然后就是高精度了

#include<cstdio>
#include<algorithm>
using namespace std;
int a[100510];
int n,tmp,nmp,x,wa,Ac,m;
int main()
{   
    scanf("%d",&Ac);
    a[1]=1,m=Ac/3;
    if(Ac%3==1) n=n+2,m=m-1;
    if(Ac%3==2) n=n+1;
    for(int i=1;i<=m;i++)
    {
        tmp=0,nmp=0,x=0;
        for(int j=100100;j>=1;j--)
            if(a[j]!=0) { tmp=j; break; }
        for(int k=1;k<=tmp;k++)
        {
            x=nmp+a[k]*3,nmp=x/10,a[k]=x%10;
            if(k==tmp&&nmp>0) tmp=tmp+1;
        }   
    }
    for(int i=1;i<=n;i++)
    {
        tmp=0,nmp=0,x=0;
        for(int j=100100;j>=1;j--)
            if(a[j]!=0) { tmp=j; break; }
        for(int k=1;k<=tmp;k++)
        {
            x=nmp+a[k]*2,nmp=x/10,a[k]=x%10;
            if(k==tmp&&nmp>0) tmp=tmp+1;
        }  
    }
    int ans=0;
    for(int i=100000;i>=1;i--)
        if(a[i]!=0) { ans=i; break; }
    printf("%d\n",ans);
    int j=max(ans-100+1,1);
    for(int i=ans;i>=j;i--) printf("%d",a[i]);
}