[水]整数拆分积

问题：对于 \(n(n\ge 3)\)，要求构造拆分 \(n=\sum_{i=1}^m a_i\)，最大化 \(\prod a_i\)。

最优情况下，满足

1. \(n\mod 3=0\)，\(a_i=3\)。

2. \(n\mod 3=2\)，\(i<m,a_i=3 ; a_m=2\)。

3. \(n\mod 3=1\)，\(i<m,a_i=3 ; a_m=4\) 或 \(i<m-1,a_i=3 ;a_{m-1}=a_m=2\)。

容易发现 \(a_i=2,a_i=4\) 的都是边界情况，我们只需要分析为何 \(a_i=3\) 能够最大化答案。

考虑由高维均值不等式 \(\displaystyle \sqrt[m]{\prod a_i}\leq \frac{\sum a_i}{m}\)，\(\displaystyle \prod a_i\leq (\frac{\sum a_i}{m})^m\)。

故知在 \(a_i\) 尽量平均时取到最值，现在只需分析\(a_i=x\)在何时取到最值。

不妨用一个函数 \(g(x)=x^{\frac{n}{x}}\) 来描述问题，

由于上标中的 \(n\) 不影响单调性，不妨分析 \(\displaystyle f(x)=g^{\frac{1}{n}}(x)=x^{\frac{1}{x}}\)。

\[ \begin{aligned} f(x)&=e^{\frac{\ln x}{x}} \\ f'(x)&=e^{\frac{\ln x}{x}}\cdot \frac{1-\ln x}{x^2} \end{aligned} \]

容易发现 \(f(x)\) 在 \(x_0=e\) 处取极大值。

由于 \(x'\in \mathbb{Z}\)，带入 \(f(2)\approx 1.414,f(3)\approx 1.442\)。

故取 \(a_i=3\)。