GESP 202603七级T1题解

userId_undefined
很烫的凉水

2026-03-14 22:49:42

发布于：广东

28阅读
0回复
0点赞

原来要写游记的，结果发现还是题解适合我
还有就是真爽， 7070 分钟创飞七级。

T1

形式化题意

tt 组数据
给定一个数 nn，随意拆成任意个数，使乘积最大，结果对 10910^9 取模。

输入

第一行一个数 tt，表示 tt 组数据。
接下来 tt 行，一行一个数，第 i+1i + 1 行表示第 ii 组数据 nn。

输出

对于每一组数据，输出可能的乘积最大值。

数据范围

对于 40%40\% 的数据保证：n≤40n \leq 40。
对于全部数据保证：t≤40，n≤106t \le 40，n \le 10^6。

思路

先给出结论：在任意情况下，尽可能的多拆出 33，并根据余数分类处理。

证明

1. 最优拆分中不会出现大于3的因子

首先可以证明，在最优的拆解方案中，拆出来的整数不会大于 33。

考虑反证法，假设最优方案中有大于等于 44 的因子 xx，那么我们可以将它拆解成 22 和 x−2x-2。通过比较拆分前后的乘积变化：

2×(x−2)=2x−42\times(x-2)=2x-4

比较 2x−42x-4 和 xx 的大小：

2x−4≥x  ⟺  x≥42x - 4 \ge x \iff x \ge 4

这意味着，如果 x≥4x \ge 4，将其拆成 22 和 x−2x-2 后，乘积不会变小，甚至更大。因此，所有大于等于 44 的因子都应该被继续分解，直到所有因子都小于等于 33 为止。

2. 最优拆分中不会出现因子1

11 对乘积无贡献，只会减少其他因子的大小，因此最优拆解方案中不会出现 11。

换句话说

x>(x−1)×1x > (x - 1) \times 1

3.论证3比2更优，并确定最终规则

既然因子只能等于 22 或 33，那么问题就转换成：在总和为 nn 的情况下，如何分配 22 和 33，使得乘积 2a×3b2^a \times 3^b 乘积最大？

很明显，在总和相同的情况下，将三个 22 替换成两个 33 总是更优。因此，在拆分中，应经可能的使用 33。

代码实现

在实际情况中，nn 不总是能被正好的全拆分成 33 需要分类讨论。

当 n mod 3=0n \bmod 3 = 0 时

可直接全部拆分成 33，顾答案为 3n33^{\frac{n}{3}}。

当 n mod 3=1n \bmod 3 = 1 时

拆分完后发现还剩下 11，与其单独拎出来浪费不如与一个 33 合并变为 44，顾答案为 3⌊n3−1⌋×43^{\left \lfloor \frac{n}{3} - 1 \right \rfloor} \times 4。

当 n mod 3=2n \bmod 3 = 2 时

拆分完后发现还剩下一个 22，单独拎出来即可，顾答案为 3⌊n3⌋×23^{\left \lfloor \frac{n}{3}\right \rfloor} \times 2

最后

GESP最新力作，七级笑传之“超超别”，直接把原题搬过来了事了，一点更改没有。深怕写过原题的不会写，没写过的能拿分。
代码就不贴了，一个快速幂和判断的事，记得特判，在 n=1n=1 时会出现 3−1×43^{-1} \times 4 的情况，显然错误。

userId_undefined
去预览
0/2000

全部评论 5

热门讨论