题解 P1249 【最大乘积】

· · 题解

update 2021-03-24:

本题解的错误部分已改正，感谢 @Rings 的指出。

题解 P1249 【最大乘积】

您正在收看的是蒟蒻 jch 的题解

题目传送门

此题解在博客中食用更佳

进入正题！

【题目大意】

把整数n分成若干个正整数的和，使这些数之积最大。

【前置知识】

贪心、数论、高精度乘法（高精\times低精）

【推导过程】

一拿到这题，就知道这是一道数学题。结论在很多题解里已经说过了：把n拆成2、3、4、5这样的连续自然数的形式。但是翻了楼上的几篇题解，貌似都没有证明。以下给出证明，其实也并不难推：

要证明这样拆是对的，其实就是证明拆出的数越多越好，因为这种拆法就是数最多（当然不包含1）的形式。而要证明拆除的数越多越好，也就是证明把两个数合并不如把两个数分开算。举个例子：9=2+3+4=5+4，我们需要证明把9拆成5+4不如把9拆成2+3+4.

设总数n=a\timesb\timesc\timesd\ldots\ldots 令k为a\timesb后面的所有数之积，则n=abk 。

如果把a与b合并，则n=(a+b)k；

现在我们的任务就是证明abk<(a+b)k。

我们可以把k提取出来，那么显然在a>1\land b>1的情况下，ab是大于a+b的。

因此，拆出数的个数越多，则乘积越大。

证毕。

【特殊情况】

然而，目前的做法并不是万能的，因为会存在有余数的情况。如：13=2+3+4+4,不够5，怎么办呢？

显然，我们需要作出一些放弃。

我采取的方法和第一篇题解一样：

先假设能全部取完，设总和为sum。

分两种情况：

【注意事项】

观察此题的数据范围，n\le10000 ？高斯告诉我们，1~100的和是5050。n=10000的结果，岂不是比100！还大？事实上，极限数据中的输出位数甚至高达243位！

于是，我们只好迫（chui）不（tou）及（sang）待（qi）地开始写高精。

还好，这里只需要写一个高精乘，还是高精乘低精，否则估计要累死。

高精乘的写法，这里就不再阐述了，毕竟太占篇幅 （太难讲，一位位乘就是了。

要注意高精首位是个位，输出要倒序。

\mathfrak{code:} 
#include<bits/stdc++.h>
#define MAXN 260 //高精位数 
#define maxn 160 //最多拆出160个数 
using namespace std;
int n;
int cnt,split[maxn]; //分别表示拆分出数的个数以及每个数的值 
struct big //高精度 
{
    int len,num[MAXN]; //答案位数和每一位的值 
}ans;
void multiply(int x) //高精乘 
{
    int t=0; //进位标志 
    for(int i=1;i<=ans.len;++i) //逐位枚举 
    {
        ans.num[i]=ans.num[i]*x+t; //每位等于两数相乘加进位 
        t=ans.num[i]/10; //处理进位 
        ans.num[i]%=10;
    }
    while(t) ans.num[++ans.len]=t%10,t/=10; //可能有乘完后位数增加的情况 
    return;
}
int main()
{
    scanf("%d",&n);
    int sum=0,now=1; //目前选中数的和、当前选择的数 
    cnt=0;
    while(sum<n) sum+=++now,split[++cnt]=now; //由2开始取（其实可以把now和cnt化成一个变量，但我觉得太麻烦了） 
    if (sum>n)//有余数 
    {
        if (sum-n==1) split[1]=-1,++split[cnt]; //第一种情况 
        else split[sum-n-1]=-1; //第二种情况，注意第1项的值是2，下标是差减一 
    }
    ans.len=1; //清空答案，由于是乘法初始值为1 
    ans.num[1]=1;
    for(int i=1;i<=cnt;++i)
        if (split[i]!=-1) printf("%d ",split[i]),multiply(split[i]); //如果没被去掉，输出并计算 
    puts("");
    for(int i=ans.len;i>=1;--i) printf("%d",ans.num[i]); //倒序输出结果 
    puts("");
    return 0; //完美结束 
}

切勿复制！

完