题解 P4157 【[SCOI2006]整数划分】

· · 题解

定理：对于给定的正整数n>2，为了将n写成若干个正整数之和，并且使这些正整数的乘积最大。只须将 n写成若干个2与3的和，并满足：

2p+3q=n.

其中，

q=(n-2p)/3.

定理的证明：设a是将n做最大乘积分解（简称最优分解）后的任一项，下面证2≤a≤4。
  1. 若a=1，设b是将n做最优分解后的另一项，则 a*b=1*b=b<1+b，即把a,b合并为一项后，总乘积会更大，故必有2≤a。
  2. 若a≥5，则容易证明这时成立：a<3(a-3)，即把a分解为两项：3与a-3之后，总和不变，而总乘积会更大，故必有a≤4。
  3. 由于4=2*2=2+2，因此最优分解中，可用2个2代替1个4。又由于2+2+2=3+3，而2*2*2<3*3，因此3个2应该用2个3代替。证毕。

补充下面证明实现的代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
int n;
class Big{
public:
    vector<int> bits;
    int cnt;
    void clear(){
        cnt=0;
        bits.push_back(1);
    }
    void mul(int n){
        for(int i=0;i<=bits.size();i++){
            bits[i]*=n;
        }
        for(int i=0;i<bits.size();i++){
            if(bits[i]>=10){
                if(i+1<bits.size())
                    bits[i+1]+=bits[i]/10;
                else{
                    bits.push_back(bits[i]/10);
                }
                bits[i]%=10;
            }
        }
    }
    void print(){
        for(int i=bits.size()-1;i>=0;i--){
            putchar('0'+bits[i]);
        }
        printf("\n");
    }
    void re(){
        reverse(bits.begin(),bits.end());
    }
    int siz(){
        return bits.size();
    }
    void choose_print(int len){
        int tot=0;
        for(int i=bits.size()-1;i;i--){
            tot++;
            putchar('0'+bits[i]);
            if(tot==len){
                break;
            }
        }
        printf("\n");
    }
}ans;
int main(){
    cin>>n;
    ans.clear();
//  cout<<21378<<endl;
    while(n>4){
        ans.mul(3);
        n-=3;   
    }   
    if(n==4){
        ans.mul(4);
    }
    if(n==3){
        ans.mul(3);
    }
    if(n==2){
        ans.mul(2);
    }
    cout<<ans.siz()<<endl;
    if(ans.siz()<=100){
        ans.print();
    }
    else{
        ans.choose_print(100);
    }
//  ans.print();
}