P1249 最大乘积 题解

Oier_point · 2025-07-31 22:28:02 · 题解

P1249 最大乘积

题意

给定一个整数 n，将 n 分解为若干个互不相同的整数，使它们乘积最大。（可以只有一个数）

分析

先从简单的情况分析起。

给定整数 n，将 n 分解为 2 个互不相同的数，设这两个数分别为 a 和 b，使 ab 最大。

我们不难想到，当 \lvert a-b \rvert 最小时，ab 最大。

这时，我们便可以想到，如果把 n 分成若干个数，是否还满足这种规律呢？

答案是肯定的，因为如果想要让乘积最大，应该让分解出来的数尽量多。

所以我们可以得出这样的思路：

• 找到一段连续的自然数，以 2 为开始，使得 2+3+4+\dots+k\ge n。

• 修正，此时如果 2+3+4+\dots+k-n 的值在 2 到 n 之间，删去即可。如果值为 1，那就将 2 与 k 删去，加入 k+1。

• 由于 3 与 4 不满足此思路，需要特判。

实现代码如下：

int now=n,i;
bool f[100001];//f[i]表示i选不选
for (i=2;i<=now;i++)
{
    f[i]=true;
    now-=i;
}
f[i]=true;
now-=i;//选k，此时now为负数
if (now==-1) //差为1
{
    f[2]=false;
    f[i]=false;
    f[i+1]=true;
}
else
{
    f[-now]=false;
}

最后由于这道题出现了大量乘法运算，所以还得写个高精度乘法。

高精度乘法：

int ans[100001]={0,1},len=1;//len为答案长度
//别忘了赋初始值 
void mul(int x)
{
    int cnt=0;//cnt为上一位的进位
    for (int i=1;i<=len;i++)
    {
        ans[i]*=x;
        ans[i]+=cnt;
        cnt=0;
        if (ans[i]>=10) //当前一位大于9，向前进位
        {
            cnt=ans[i]/10;
            ans[i]%=10;
        }
    }
    ans[len+1]+=cnt;
    //如果最高位前面有新加上来的数，就更新位数 
    while (ans[len+1]!=0)
    {
        len++;
        ans[len+1]+=(ans[len]/10);
        ans[len]%=10;
    }
}

最后拼起来就是 AC 代码了。

ACcode：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n,ans[100001]={0,1},len=1;//len为答案长度
bool f[100001];
//别忘了赋初始值 
void mul(int x)
{
    int cnt=0;//cnt为上一位的进位
    for (int i=1;i<=len;i++)
    {
        ans[i]*=x;
        ans[i]+=cnt;
        cnt=0;
        if (ans[i]>=10) //当前一位大于9，向前进位
        {
            cnt=ans[i]/10;
            ans[i]%=10;
        }
    }
    ans[len+1]+=cnt;
    //如果最高位前面有新加上来的数，就更新位数 
    while (ans[len+1]!=0)
    {
        len++;
        ans[len+1]+=(ans[len]/10);
        ans[len]%=10;
    }
}
int main()
{
    cin>>n;
    if (n<=4) 
    {
        cout<<n<<"\n"<<n;
        return 0;
    }
    ll now=n,i;
    for (i=2;i<=now;i++)
    {
        f[i]=true;
        now-=i;
    }
    f[i]=true;
    now-=i;//选k，此时now为负数
    if (now==-1) //差为1
    {
        f[2]=false;
        f[i]=false;
        f[i+1]=true;
    }
    else
    {
        f[-now]=false;
    }
    for (int j=2;j<=i+1;j++)
    {
        if (f[j]) //选就输出并乘上答案
        {
            cout<<j<<" ";
            mul(j);
        }
    }
    cout<<"\n";
    for (int i=len;i>=1;i--)
    {
        cout<<ans[i];
    }
    return 0;
}