题解：P15802 [GESP202603 七级] 拆分

lcliruiyan · 2026-03-16 10:41:33 · 题解

题目大意

给出 a_1+a_2+\dots+a_k 的和 n，求 a_1 \times a_2 \times \dots \times a_n 的最大值。

题目思路

::::info[一个比较基础的结论]{open} 当一些数的和一定时，每个数之间的差越小，这些数的乘积越大。

:::info[证明] 我们可以先证明只有两个数的情况。设 a+b=S，S 为定值，则 b=S-a。那么：

这是一个二次函数，由于二次项系数为负数，所以抛物线开口朝下。由于 S 为定值，所以 \dfrac{S^2}{4} 也为定值。因此，该函数在 a=\dfrac{S}{2} 时取最大值。此时 a=b，也就是这两个数的差值最小。

接下来将结论推广到多个数的情况。设 x_1+x_2+\dots+x_n=S，S 为定值，取 x_i \ne x_j，再令 x_a+x_b=x_i+x_j 且 x_a=x_b。那么 x_a \times x_b = (\dfrac{x_i+x_j}{2})^2 > x_i \times x_j，也就是均值不等式。

所以整体乘积变大。 ::: ::::

因此，我们要让所有的 a_i 差值尽量小。

根据我在考场上大量的暴力输出尝试和推算，我找出来一个规律：当乘积最大时，a_i 一定是 2 或 3。

::::info[证明如下]{open} 我们先找一个 a_i>3，然后分类讨论。

当 a_i=4 时，a_i=2+2=2 \times 2。

当 a_i \ge 5 时，a_i=2+(a_i-2)，2 \times (a_i-2)=2 \times a_i-4>a_i。

因此，a_i \le 3 一定较优。

又因为 a_i=1 时，不会改变乘积，所以 a_i=1 一定更劣。

所以 a_i 等于 2 或 3。 ::::

若 n=6，a_i 有两种情况：a_1=a_2=a_3=2 或 a_1=a_2=3。第一种情况的乘积为 8，第二种情况的乘积为 9。因此可以推出，3 的贡献会比 2 更大，因此要尽量多选 3。

那么就可以分三种情况讨论。

这样就能使 3 的个数尽量多了。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long//不开long long见祖宗
const int mod=1e9;//别忘记取模！！！
int t,n;
int qpow(int a,int b)//快速幂
{
    if(b==0)return 1;
    if(b==1)return a;
    int hf=qpow(a,b/2)%mod;
    int sum=(hf*hf)%mod;
    if(b%2==1)sum=(sum*a)%mod;
    return sum;
}
signed main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        if(n<=3)cout<<n<<endl;//n=1,2,3时都不能再拆
        else
        {
            if(n%3==0)cout<<qpow(3,n/3)<<endl;
            if(n%3==1)cout<<(4*qpow(3,(n-4)/3))%mod<<endl;
            if(n%3==2)cout<<(2*qpow(3,(n-2)/3))%mod<<endl;
        }
    }
    return 0;
}

其实本蒟蒻是在考场上暴力输出然后瞪眼瞪出来的。