尽量多拆 3,余数用 2 或 4 补齐,快速幂取模 10⁹。
把一个正整数 n 拆分成若干个正整数之和(a₁ + a₂ + … + a_k = n,1 ≤ k ≤ n),使拆分后的乘积 a₁ × a₂ × … × a_k 最大。由于答案可能很大,只需输出最大值对 10⁹ 取模的结果。
输入第一行是数据组数 t,接下来 t 行每行一个正整数 n;每组输出一行答案。
1 × x = x,白占一个名额)。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,也不是质数) |
k ≥ 5 有 3 × (k−3) ≥ k,说明把大因子拆出一个 3 一定不会变差;再配合"1 不该出现"和"三个 2 换两个 3",因子就只剩 2 和 3 了n = 4 要拆成 2 + 2?因为 3 + 1 = 4 的乘积是 3,而 2 + 2 = 4 的乘积是 4,后者更大——余数 1 要靠"借 4"来消化O(log n) 跑 t ≤ 10⁴ 组绰绰有余先看小数据的最优拆法,再算大数据。
| n | 最优拆法 | 乘积 | 对应公式 |
|---|---|---|---|
| 5 | 3 + 2 | 6 | r = 2 → 3¹ × 2 |
| 8 | 3 + 3 + 2 | 18 | r = 2 → 3² × 2 |
| 100 | 3 + 3 + … + 3(32 个 3)+ 4 | 755407364(取模后) | r = 1 → 3³² × 4 |
5 mod 3 = 2 → 补一个 2
3 的个数 = (5 − 2) / 3 = 1
拆法 3 + 2,乘积 6
对比:4 + 1 → 4,5 → 5,2 + 3 → 6(最优)
✅ 6
8 mod 3 = 2 → 补一个 2
3 的个数 = (8 − 2) / 3 = 2
拆法 3 + 3 + 2,乘积 18
对比:4 + 4 → 16,3 + 5 → 15(都不如 18)
✅ 18
100 mod 3 = 1,不能直接全拆 3(会剩一个 1)
所以要留出一个 4(= 2 + 2)来消化余数
3 的个数 = (100 − 4) / 3 = 32
3³² = 1853020188851841
3³² × 4 = 7412080755407364
对 10⁹ 取模 = 755407364
✅ 755407364
… × 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"。把"该拆什么"逐条比较一遍,结论就无可辩驳了。
| 原始因子 / 拆法 | 拆前贡献 | 拆后贡献 | 结论 |
|---|---|---|---|
| 6 = 3 + 3 | 6 | 9 | 拆出 3 更好 |
| 6 = 2 + 2 + 2 | 8(另一种拆法) | 9(= 3 + 3) | 三个 2 换成两个 3 更好 |
| 4 = 2 + 2 | 3(= 3 + 1 的乘积) | 4 | 别留 1,用 2 + 2 |
| 5 = 3 + 2 | 5(不拆) | 6 | 拆出 3 更好 |
| 7 = 3 + 4 | 7(不拆) | 12 | 拆出 3 更好 |
| 8 = 3 + 3 + 2 | 16(= 4 + 4) | 18 | 拆成 3 / 2 更好 |
若某一项 k ≥ 5,把它换成 3 + (k−3):
3 × (k−3) − k = 2k − 9 ≥ 1 > 0(k ≥ 5 时)
所以任何 ≥ 5 的因子都该继续拆
最终因子只会是 1、2、3、4
✅ 大因子全部拆掉
1 × x = x,保留 1 不产生任何增益
把 1 并到任意一项 x ≥ 2 上:x + 1 > x × 1
所以 1 永远不该单独出现
4 就是"1 与 3 合并"的最好归宿(= 2 + 2)
✅ 只剩 2 和 3 与 4
若出现三个 2:2³ = 8
换成两个 3:3² = 9 > 8
所以 2 最多出现两个
最终形状:3^a ×(1 / 2 / 4)
1 不出现,所以只用 2 或 4
✅ 三种余数情形确定
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 次幂(还可能在整除里踩坑)。n ≥ 5 时按 n mod 3 分三类,用快速幂求 3 的幂再乘 2 或 4
(a × b) mod m = ((a mod m) × (b mod m)) mod m)。先把 pow3[i] = 3^i mod 10⁹ 全算出来,每组 O(1) 查表
| 方案 | 复杂度 | 能否通过 |
|---|---|---|
| 贪心分类 + 快速幂 | O(t log n) ≈ 2 × 10⁵ | ✅ 推荐 |
| 预处理幂表 | O(maxN + t) | ✅ 可行(多用一个数组) |
| 每组跑一遍 DP | O(t · n) ≈ 10¹⁰ | ❌ 严重超时 |
输入一个 n(1 ≤ n ≤ 10⁶),程序给出最优拆法、最大乘积的幂形式与对 10⁹ 取模的结果。
点按钮开始 →
#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) × 4 | r = 1 | 借 4 消化余数(3 + 1 换成 2 + 2) |
n % 3 == 2 → qpow(3,(n−2)/3) × 2 | r = 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 存中间乘积;⑤ 多组数据漏读 / 漏换行。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 | 6 18 755407364 | 题面样例 1 |
1 | 1 | n = 1:只能拆成 1 |
1 | 4 | n = 4:2 + 2 = 4(比 3 + 1 的 3 大) |
2 | 9 12 | 6 → 3 + 3;7 → 3 + 4 |
1 | 846071364 | n = 10⁶(r = 1,快速幂承担全部工作量) |
n ≤ 4 特判了吗?③ r = 1 借 4 了吗?④ 用快速幂了吗?10⁹,不是 10⁹+7。r = 1 分支,算出 3 的 −1 次幂(C++ 整除得 −1,qpow 返回 1),结果错成 4。×1 会漏掉那一份收益。全程只用几个 long long 变量,没有数组、没有递归,空间是常数。
✅ 几十万次操作,瞬间完成。相比"每组跑一遍 O(n) 的 DP"(合计 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 万位,这就是为什么题目一定要你取模。)