【bzoj1263】整数划分(写于WC第一天)

2015.02.08 16:45 Sun | 8次阅读 | 旧日oi | 固定链接 | 源码

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

题解

 小学奥数题。。证明请看http://blog.csdn.net/popoqqq/article/details/43602567
水题一个,就是学一下结构体内重载运算符的方法……

我的程序

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int n;
struct cbig{
    int num[5500],len;
    cbig(int x)
    {
        num[++len]=x;
    }
    void operator *=(int x)
    {
        for(int i=1;i<=len+1;i++) 
        {
            num[i]*=x;
            num[i]+=num[i-1]/10;
            num[i-1]%=10;
        }
        while(num[len+1]) len++,num[len+1]=num[len]/10,num[len]%=10;
    }
}ans(1);
int main()
{
    cin>>n;
    switch(n%3)
    {
        case 0:for(int i=3;i<=n;i+=3) ans*=3;break;
        case 1:ans*=4;for(int i=3;i<=n-4;i+=3) ans*=3;break;
        case 2:ans*=2;for(int i=3;i<=n-2;i+=3) ans*=3;break;
    }
    cout<<ans.len<<endl;
    for(int i=ans.len;i&&i>ans.len-100;i--)
    cout<<ans.num[i];
}```