拆分 题解

题目分析

给定正整数 $n$，需要将其拆分成若干个正整数之和，目标是最大化这些正整数的乘积。题目要求输出乘积最大值对 $10^9$ 取模的结果。数据范围中 $n$ 最大可达 $10^6$，且有多组询问。

若直接计算乘积，数值会极大（指数级增长），无法用标准整数类型存储。但题目只需要取模后的结果。然而取模后会丢失数值的大小关系，无法简单地用模后的值来比较哪种拆分更优。因此需要一种既能够比较乘积大小，又能正确输出模值的方法。

解题思路

经典结论

整数拆分最大化乘积问题有一个广为人知的结论：

• 当 $n \le 4$ 时，不拆分（即 $k=1$，本身即为一个数）能得到最大乘积 $n$。
• 当 $n>4$ 时，应尽可能多地拆分出 $3$，剩余部分若为 $1$，则将一个 $3$ 与 $1$ 合并成两个 $2$（因为 $2\times 2=4>3\times 1=3$）；若剩余 $2$，则保留一个 $2$。

换句话说，最优拆分只包含数字 $2$ 和 $3$，且 $2$ 的个数不超过 $2$ 个。

DP 解法（基于对数的比较）

由于 $n$ 很大，乘积会超过标准类型的表示范围，即使使用高精度也会导致时间和空间开销过大。但我们可以利用对数的性质：

取对数后，乘积的“大小”变成了对数值的“和”，而对数值是容易存储和比较的浮点数。同时，我们用一个独立的数组存储乘积取模后的值（模 $10^9$），这样既能正确比较优劣，又能输出答案。

状态定义：

• f[i]：和为 $i$ 时的最大乘积对 $10^9$ 取模的结果。
• lnf[i]：该最大乘积的自然对数值，用于大小比较。

初始化：

• f[0] = f[1] = 1（和为 $0$ 或 $1$ 时，乘积看作 $1$，作为递推起点）。
• lnf[0] = lnf[1] = 0。

转移：

从当前和 $i$ 出发，尝试添加一个 $2$ 或一个 $3$：

• 添加 $2$：新和 $i+2$，乘积变为 f[i] * 2，对数值变为 lnf[i] + ln2。若该值大于已有的 lnf[i+2]，则更新 f[i+2] 和 lnf[i+2]。
• 添加 $3$：同理，考虑 $i+3$，对数值增加 ln3。

由于 $1$ 在最优拆分中几乎不会出现（除了 $n=1$ 时默认值），且任何大于 $4$ 的数拆成 $2,3$ 会使乘积更大，上述转移足以覆盖所有情况。

最终对于每个询问 $n$，直接输出 f[n] 即可。

这种做法的本质是用 DP 实现了贪心策略，同时绕开了大数比较的难题。

算法说明

1. 预处理从 $0$ 到 $10^6$ 的所有 f 和 lnf。
2. 外层循环枚举当前和 $i$，内层尝试添加 $2$ 和 $3$，以对数值的大小作为转移依据。
3. 对每组询问 $O(1)$ 输出结果。

时间复杂度分析

• 预处理：循环 $O(N)$ 次，每次常数操作，$N = 10^6$，可以接受。
• 询问：$t \le 10^4$，每次 $O(1)$。

总时间复杂度 $O(N + t)$，空间复杂度 $O(N)$，在时间和内存限制内均能顺利运行。

参考代码

cpp
复制
1#include <cstdio>
2#include <cmath>
3#include <algorithm>
4using namespace std;
5const int N = 1e6 + 5;
6const int mod = 1e9;
7const double ln2 = log(2);
8const double ln3 = log(3);
9int f[N];
10double lnf[N];
11
12int main() {
13    f[0] = f[1] = 1;
14    // lnf 全局默认为 0，而有效乘积的对数均为非负数，因此 0 可作为未访问标记。
15    for (int i = 0; i < N; i++) {
16        // 尝试添加 2
17        if (i + 2 < N && lnf[i] + ln2 > lnf[i + 2]) {
18            lnf[i + 2] = lnf[i] + ln2;
19            f[i + 2] = 2ll * f[i] % mod;
20        }
21        // 尝试添加 3
22        if (i + 3 < N && lnf[i] + ln3 > lnf[i + 3]) {
23            lnf[i + 3] = lnf[i] + ln3;
24            f[i + 3] = 3ll * f[i] % mod;
25        }
26    }
27    int t;
28    scanf("%d", &t);
29    while (t--) {
30        int n;
31        scanf("%d", &n);
32        printf("%d\n", f[n]);
33    }
34    return 0;
35}

代码解释

• ln2 和 ln3 分别预计算了 $\ln 2$ 和 $\ln 3$，避免重复调用 log 函数。
• f[i] 存储当前最大乘积取模后的值，lnf[i] 存储该乘积的自然对数。
• 转移时通过 lnf[i] + ln2 与当前 lnf[i+2] 比较，若更大则更新，保证每个状态存储的都是最优值。
• 由于 $1 \le t \le 10^4$ 且 $n \le 10^6$，预处理后每个询问直接输出即可。
• 注意取模常数为 $10^9$，并非通常的 $10^9+7$。

补充：贪心解法简述

如果仅需回答单次或少量询问，也可以直接使用数学结论：

• 若 $n = 1$，答案为 $1$。
• 若 $n = 2$，答案为 $2$（或不拆分得 $2$，拆为 $1+1$ 得 $1$，取大）。
• 若 $n = 3$，答案为 $3$。
• 若 $n = 4$，答案为 $4$。
• 若 $n>4$：
  • 当 $n \bmod 3 = 0$ 时，全拆为 $3$。
  • 当 $n \bmod 3 = 1$ 时，拆出两个 $2$，其余全为 $3$。
  • 当 $n \bmod 3 = 2$ 时，拆出一个 $2$，其余全为 $3$。

用快速幂计算结果并取模即可，复杂度同样优秀。但本题中 DP 方法更具一般性且思路清晰，也能很好地应对取模后无法比较大小的难点。