GESP 题解库 / 7 级题解 / [GESP202603 七级] 拆分 · 第 2 / 24 题
GESP202603 七级 · P15802 · 中等

整数拆分求最大乘积

尽量多拆 3,余数用 2 或 4 补齐,快速幂取模 10⁹。

🔢
t ≤ 10⁴、n ≤ 10⁶
数据规模
🎯
模数 10⁹
不是 10⁹+7
⚡
O(t log n)
快速幂
✂️
贪心:尽量拆 3
核心结论
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

把一个正整数 n 拆分成若干个正整数之和(a₁ + a₂ + … + a_k = n,1 ≤ k ≤ n),使拆分后的乘积 a₁ × a₂ × … × a_k 最大。由于答案可能很大,只需输出最大值对 10⁹ 取模的结果。

输入第一行是数据组数 t,接下来 t 行每行一个正整数 n;每组输出一行答案。

💡
人话翻译:这是"整数拆分求最大乘积"的经典结论题。
直觉上"拆得越碎乘积越大",但拆到 1 反而亏(1 × x = x,白占一个名额)。
结论是:尽量多拆出 3。因为任意一项 k ≥ 5 都能改写成 3 + (k−3),而 3(k−3) ≥ k,所以大于 4 的因子全都不划算。
剩下的特例很干净:1→1、2→2、3→3、4→2+2。
n ≥ 5 时按 n mod 3 分三种情况,用快速幂算 3 的幂即可。

🔍 关键词提取

贪心结论尽量拆 3按余数分类快速幂模 10⁹

已知条件

项目说明
输入第一行 t;随后 t 行,每行一个 n
输出每组一行,最大值对 10⁹ 取模
数据范围1 ≤ t ≤ 10⁴,1 ≤ n ≤ 10⁶
部分分40% 的测试点保证 n ≤ 50
模数10⁹(不是 10⁹+7,也不是质数)

需要解决的问题

02
思维导图
整理解题思路的全貌
✂️ 尽量拆成 3,余数用 2 / 4 补齐
🧠 核心结论
任意 k ≥ 5:拆出 3 更优
3 × (k−3) ≥ k ⟺ k ≥ 4.5
因子只会是 2 和 3(4 即 2+2)
因子 1 永远不出现
📐 小数据特判
n = 1 → 1
n = 2 → 2
n = 3 → 3
n = 4 → 2 + 2 = 4
🔢 按余数分类(n ≥ 5)
n mod 3 = 0 → 3^(n/3)
n mod 3 = 1 → 3^((n−4)/3) × 4
n mod 3 = 2 → 3^((n−2)/3) × 2
幂用快速幂求
⚠️ 易错点
模数写成 10⁹+7
n = 1 未特判(会算 3 的负次幂)
r = 1 时误写成 ×1
乘法用 int / double 溢出
03
样例手算推导
样例与"为什么 3 最好"的完整推演

🧮 样例:n = 5、8、100

先看小数据的最优拆法,再算大数据。

n最优拆法乘积对应公式
53 + 26r = 2 → 3¹ × 2
83 + 3 + 218r = 2 → 3² × 2
1003 + 3 + … + 3(32 个 3)+ 4755407364(取模后)r = 1 → 3³² × 4
1
n = 5:r = 2

5 mod 3 = 2 → 补一个 2

3 的个数 = (5 − 2) / 3 = 1

拆法 3 + 2,乘积 6

对比:4 + 1 → 4,5 → 5,2 + 3 → 6(最优)

✅ 6

2
n = 8:r = 2

8 mod 3 = 2 → 补一个 2

3 的个数 = (8 − 2) / 3 = 2

拆法 3 + 3 + 2,乘积 18

对比:4 + 4 → 16,3 + 5 → 15(都不如 18)

✅ 18

3
n = 100:r = 1,要"借 4"

100 mod 3 = 1,不能直接全拆 3(会剩一个 1)

所以要留出一个 4(= 2 + 2)来消化余数

3 的个数 = (100 − 4) / 3 = 32

3³² = 1853020188851841

3³² × 4 = 7412080755407364

对 10⁹ 取模 = 755407364

✅ 755407364

🔑
为什么 r = 1 要"借 4"而不是"留 1"?因为 … × 3 × 1 里的 1 白白浪费了一个名额。把 3 + 1 这一对换成 2 + 2:3 × 1 = 3,而 2 × 2 = 4,白白多赚 1。
所以 n mod 3 = 1 时,答案写成 3^((n−4)/3) × 4,等价于"拿出一个 3 和余数 1 合并成 4"。

🧮 为什么"3 是最好的因子"?

把"该拆什么"逐条比较一遍,结论就无可辩驳了。

原始因子 / 拆法拆前贡献拆后贡献结论
6 = 3 + 369拆出 3 更好
6 = 2 + 2 + 28(另一种拆法)9(= 3 + 3)三个 2 换成两个 3 更好
4 = 2 + 23(= 3 + 1 的乘积)4别留 1,用 2 + 2
5 = 3 + 25(不拆)6拆出 3 更好
7 = 3 + 47(不拆)12拆出 3 更好
8 = 3 + 3 + 216(= 4 + 4)18拆成 3 / 2 更好
1
第 1 步:排除 k ≥ 5 的因子

若某一项 k ≥ 5,把它换成 3 + (k−3):

3 × (k−3) − k = 2k − 9 ≥ 1 > 0(k ≥ 5 时)

所以任何 ≥ 5 的因子都该继续拆

最终因子只会是 1、2、3、4

✅ 大因子全部拆掉

2
第 2 步:排除因子 1

1 × x = x,保留 1 不产生任何增益

把 1 并到任意一项 x ≥ 2 上:x + 1 > x × 1

所以 1 永远不该单独出现

4 就是"1 与 3 合并"的最好归宿(= 2 + 2)

✅ 只剩 2 和 3 与 4

3
第 3 步:2 的个数 ≤ 2

若出现三个 2:2³ = 8

换成两个 3:3² = 9 > 8

所以 2 最多出现两个

最终形状:3^a ×(1 / 2 / 4)

1 不出现,所以只用 2 或 4

✅ 三种余数情形确定

⚠️
把结论压缩成一张表(n ≥ 5):
· n mod 3 = 0 → 3^(n/3);
· n mod 3 = 1 → 3^((n−4)/3) × 4(借 4);
· n mod 3 = 2 → 3^((n−2)/3) × 2(补 2)。
注意小数据 n = 1 必须单独输出 1,否则按 r = 1 分支会算出 3 的 −1 次幂(还可能在整除里踩坑)。
04
解法对比
贪心分类 + 快速幂 vs 预处理幂表

⚔️ 解法对比

🟢 贪心分类 + 快速幂(推荐) 推荐

n ≥ 5 时按 n mod 3 分三类,用快速幂求 3 的幂再乘 2 或 4

  • 每组 O(log n)
  • t = 10⁴ 时约 2 × 10⁵ 次乘法
  • 代码约 20 行
  • 不需要任何额外数组
💡
为什么能直接取模?乘法和幂在模意义下都可以边算边取模((a × b) mod m = ((a mod m) × (b mod m)) mod m)。
本题没有除法,所以模数 10⁹ 不是质数也完全不影响——不需要逆元,也不需要 10⁹+7。

🟠 预处理 3 的幂表

先把 pow3[i] = 3^i mod 10⁹ 全算出来,每组 O(1) 查表

  • 预处理 O(maxN/3)
  • 每组 O(1)
  • 思路非常直白
  • 要开一个约 3.4 × 10⁵ 的数组
⚠️
也很好,两种都对:预处理版本把"所有幂"一次性算完,适合 t 很大而 n 较小的情形。
缺点是必须知道 n 的最大值才能开数组;而快速幂版本对任意 n 都是 O(log n),更通用、也不需要额外空间。

📈 性能对比

方案复杂度能否通过
贪心分类 + 快速幂O(t log n) ≈ 2 × 10⁵✅ 推荐
预处理幂表O(maxN + t)✅ 可行(多用一个数组)
每组跑一遍 DPO(t · n) ≈ 10¹⁰❌ 严重超时
05
算法流程图
每组询问的处理流程
开始读入数据组数 t处理下一组询问:读入 nn ≤ 4 吗?是 ✓直接输出 n(n = 4 视为 2 + 2)否 ✗看 n mod 3 的余数n mod 3 的余数是?r = 0 → 3^(n/3)r = 1 → 3^((n−4)/3) × 4r = 2 → 3^((n−2)/3) × 2用快速幂算幂结果对 10⁹ 取模后输出还有询问没处理吗?结束下一组询问
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

✂️ 最大乘积拆分器

输入一个 n(1 ≤ n ≤ 10⁶),程序给出最优拆法、最大乘积的幂形式与对 10⁹ 取模的结果。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(分类 + 快速幂)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1000000000LL;      // 10^9,注意不是 10^9+7

ll qpow(ll a, ll e) {             // 快速幂:a^e mod MOD
    ll r = 1;
    a %= MOD;
    while (e > 0) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        ll n;
        scanf("%lld", &n);

        ll ans;
        if (n == 1)            ans = 1;
        else if (n == 2)       ans = 2;
        else if (n == 3)       ans = 3;
        else if (n == 4)       ans = 4;                            // 2 + 2
        else if (n % 3 == 0)   ans = qpow(3, n / 3);               // 全拆 3
        else if (n % 3 == 1)   ans = qpow(3, (n - 4) / 3) * 4 % MOD; // 借一个 4
        else                   ans = qpow(3, (n - 2) / 3) * 2 % MOD; // 补一个 2

        printf("%lld\n", ans);
    }
    return 0;
}
🔑
注意 qpow 里的乘法为什么不会溢出:所有中间值都先对 10⁹ 取模,所以每次乘的两个数都小于 10⁹,乘积小于 10¹⁸,稳稳落在 long long(约 9.2 × 10¹⁸)里。
但如果模数换成 10⁹+7 也照样安全;真正危险的是忘记取模——比如 qpow(3, n/3) 后面直接乘 4 却不取模。

📖 关键几行怎么看

代码作用为什么这样写
const ll MOD = 1000000000LL;模数题目给的是 10⁹,别写成 10⁹+7
if (n == 1) ans = 1;特判n = 1 走通用分支会算 3^(−1),必须先拦下
n % 3 == 0 → qpow(3, n/3)r = 0全部拆成 3
n % 3 == 1 → qpow(3,(n−4)/3) × 4r = 1借 4 消化余数(3 + 1 换成 2 + 2)
n % 3 == 2 → qpow(3,(n−2)/3) × 2r = 2补一个 2
a = a * a % MOD;快速幂核心指数每次折半,O(log e)
⚠️
五个坑:① 模数写成 10⁹+7;② n = 1 没特判((1−4)/3 在 C++ 里是 −1,qpow 会直接返回 1,答案错成 4);③ r = 1 时写成 ×1 或 3^((n−1)/3);④ 用 int 存中间乘积;⑤ 多组数据漏读 / 漏换行。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3
5
8
100
6
18
755407364
题面样例 1
1
1
1n = 1:只能拆成 1
1
4
4n = 4:2 + 2 = 4(比 3 + 1 的 3 大)
2
6
7
9
12
6 → 3 + 3;7 → 3 + 4
1
1000000
846071364n = 10⁶(r = 1,快速幂承担全部工作量)
✅
自查清单:① 模数是 10⁹ 吗?② n ≤ 4 特判了吗?③ r = 1 借 4 了吗?④ 用快速幂了吗?

🚨 易错点清单

⚠️
模数写错:题目是 10⁹,不是 10⁹+7。
⚠️
漏特判 n = 1:会掉进 r = 1 分支,算出 3 的 −1 次幂(C++ 整除得 −1,qpow 返回 1),结果错成 4。
⚠️
r = 1 处理错:必须"借 4",写成 ×1 会漏掉那一份收益。
⚠️
溢出:中间乘积要先取模,用 long long。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(t log n)
空间复杂度
O(1)
t 最大
10⁴
运算量
约 2 × 10⁵ 次乘法

时间怎么算的?

空间都用在哪?

全程只用几个 long long 变量,没有数组、没有递归,空间是常数。

✅ 几十万次操作,瞬间完成。相比"每组跑一遍 O(n) 的 DP"(合计 10¹⁰),快了五个数量级。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 整数拆分最大乘积:结论速记
// n = 1 -> 1     n = 2 -> 2     n = 3 -> 3     n = 4 -> 2 + 2 = 4
// n >= 5 时按 n % 3 分类:
//   r = 0 -> 3^(n/3)
//   r = 1 -> 3^((n-4)/3) * 4      // 借一个 4 = 2 + 2 消化余数
//   r = 2 -> 3^((n-2)/3) * 2      // 补一个 2

// 为什么因子只剩 2 和 3?
// (1) k >= 5 时 3 * (k - 3) >= k  -> 任何 >= 5 的因子都该拆出 3
// (2) 因子 1 永不出现:1 * x == x,白占一个名额
// (3) 2 的个数 <= 2:2^3 == 8 < 3^2 == 9,三个 2 换两个 3 更优

// 快速幂模板(中间乘积必须先取模)
ll qpow(ll a, ll e, ll mod){
    ll r = 1; a %= mod;
    while (e > 0) { if (e & 1) r = r * a % mod; a = a * a % mod; e >>= 1; }
    return r;
}

// 模数提醒:本题是 10^9(不是 10^9+7),并且全程没有除法,
// 所以不需要逆元,模数是不是质数都无所谓

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
贪心证明用 3(k−3) ≥ k 排除大因子整数拆分、找零、均分类贪心结论
按余数分类按 n mod 3 分三种情形环形 / 周期类构造题
快速幂O(log e) 求 3 的幂取模幂、矩阵快速幂的通用模板
特判小数据n ≤ 4 单独处理所有"结论有例外"的构造题
🌟
思考题:如果题目不取模,要求输出精确的最大乘积,做法要怎么改?(提示:结论完全一样,仍按三类算出 3^e × 2 或 × 4,只是需要高精度乘法(Python 的大整数、或 C++ 手写高精度 / 压位)。答案的位数约为 0.477 × n 位——n = 10⁶ 时约 48 万位,这就是为什么题目一定要你取模。)