自动搬运

查看原文

来自洛谷，原作者为

	劉子颺 **

搬运于2025-08-24 21:57:07，当前版本为作者最后更新于2018-02-27 13:30:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

定理：对于给定的正整数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();
}