描述

整数分解(版本2)

一个正整数可以分解成若干个自然数之和。请你编一个程序，对于给出的一个正整数n(1<=n<=1500)，求出满足要求的分解方案，并使这些自然数的乘积m达到最大。

例如n=10，则可以分解为2+2+3+3，乘积m=2*2*3*3=36

格式

输入格式

一个正整数n

输出格式

输出分解的自然数的最大乘积m

样例1

样例输入1

10

样例输出1

36

题解

通过对这道题的分析，可以发现：

如果n1,2,3,则不用分；

如果n=4，则分成两个2和部分都是一样的；

如果n5，则分成2和3是最大的；

如果n6，则分成3和3是最大的；

如果n7，则分成4和3是最大的；

如果n8，则分成2和3和3是最大的；

如果n9，则分成3和3和3是最大的；

……

总结规律，我们可以发现如果一个数大于4的情况下，我们只要不断地分3就可以了。而这就是我们的解法。

代码如下：

#include <cstdio>

#include <cstring>

using namespace std;

int a[1500], n;

void init()

{

    memset(a, 0, sizeof(a));

    a[0] = 1;

}

void  multi(int b)

{

    int c = 0;

    for (int i = 0; i < 1500; i ++)

    {

        c = c + a[i] * b;

        a[i] = c % 10;

        c /= 10;

    }

}

void output()

{

    int i = 1499;

    for (;i > 0 && a[i] == 0; i --);

    for (;i >= 0; i --)

    {

        printf("%d", a[i]);

    }

    printf("\n");

}

int main()

{

    init();

    scanf("%d", &n);

    while (n > 4)

    {

        n -= 3;

        multi(3);

    }

    multi(n);

    output();

    return 0;

}

这里唯一要考虑的问题是n<=1500，所以答案最大可能达到3^500，这是long long类型都保存不了的，所以需要用到大数乘法。