题解：P15802 [GESP202603 七级] 拆分

· · 题解

随机跳题随到的，结果拼尽全力艰难证明 /ll

省流：尽可能多地拆分出 3。

在这个结论基础上，容易得到本题的做法：

容易快速幂实现做到 O(T \log n)，或者预处理幂次做到 O(n+T)，代码不放了。下面我们来证明这个结论。

首先我们有一些显然的观察： - 拆分方案中不会包含 $1$。 - 拆分方案中的 $4$ 可以被视为两个 $2$。 下证：拆分方案中不会包含 $\ge 5$ 的数。 设 $x \ge 5$，我们可以将其拆分为 $3$ 和 $x-3$，乘积为 $3(x-3)$。作差：$3(x-3)-5=3x-14 > 0$，故调整更优。 这样只需对 $2$ 和 $3$ 讨论。 下证：拆分方案中至多包含两个 $2$。 假设 $x_1=x_2=x_3=2$，其和为 $6$，乘积为 $8$。调整为 $x_1=x_2=3$，和不变，乘积为 $9$，调整更优。 综上，拆分方案中至多包含两个 $2$，且只会包含 $\le 4$ 的数，证毕。 上面是离散角度的说明。我们还可以从连续的角度来说明： 扩展到 $n \in \mathbb{R}$ 的情形。根据柯西不等式，所有数全相等是更优秀的。于是设这些数都是 $x$，构造函数 $f(x)=x^{n/x}$，则需找到 $f(x)$ 的最大值。 注意到 $n$ 的取值与 $f(x)$ 取得最大值的位置无关，于是取 $n=1$ 有 $f(x)=x^{1/x}$。 考虑求导 $$ \begin{aligned} f(x) &= x^{1/x}\\ \ln f(x) &= \ln x^{1/x}=\dfrac{1}{x} \ln x\\ (\ln f(x))' &= -\dfrac{1}{x^2} \ln x + \dfrac{1-\ln x}{x^2}\\ \dfrac{1}{f(x)} f'(x) &= \dfrac{1-\ln x}{x^2}\\ f'(x)&= \dfrac{x^{1/x}(1-\ln x)}{x^2} \end{aligned} $$ 令 $f'(x)=0$，注意到 $x_1=0,x_2=e$ 为两个解，其中 $x=0$ 是平凡的，舍去。 不难证明 $x<e$ 时 $1 -\ln x >0$，则 $f'(x)>0$，同理 $x>e$ 时 $f'(x)<0$，因此在 $(0,+\infty)$ 上 $f'(x)=0$ 有且仅有 $x=e$ 一个解。则 $f(x)=x^{n/x}$ 的最大值为 $f(e)=e^{n/e}$。 当定义域改为 $\mathbb{N}^+$ 时，注意到 $$ \begin{aligned} \int_{2}^e f(x) dx &>1\\ \int_e^3 f(x) dx &<1\\ \int_{2}^e f(x) dx &>\int_e^3 f(x) dx\\ f(2) &> f(3) \end{aligned} $$ 于是 $f(x)$ 的最小值为 $f(3)=3^{n/3}$。 [P5972](https://www.luogu.com.cn/problem/P5972) 的复杂度用到了这个题的结论，分析出来是 $O(n^2 3^{n/3})$。有兴趣可以去做一下。