从 2 开始拆成尽量多的互不相同自然数，再把剩余值从大到小分散加回以最大化乘积。
OJ: luogu
题目 ID: P1249
难度:普及-
标签:贪心高精度python
日期: 2026-07-15 22:10
题意
把正整数 n 拆成若干个互不相同的自然数之和，使这些数的乘积最大。输出拆分方案和最大乘积。
思路
乘积最大时，应尽量拆成多个接近的数，并避免使用 1。因此从 2,3,4,... 开始尽量取：
text
2 + 3 + 4 + ...直到再取下一个数会超过 n。此时剩下 remaining，把它从当前较大的数开始每次加 1 分散回去。
例如 n=10：
text
先取 2,3,4，和为 9，剩 1
把 1 加到最大数 4 上，得到 2,3,5这样仍然互不相同，并且数值尽量均衡。乘积可能很大，但 Python 大整数可以直接计算。
Python 知识
/home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md：Python 整数不会溢出，适合计算大乘积。/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：print(*parts)按空格输出方案。- 列表可以从末尾向前循环分配剩余量。
代码
python
n = int(input())
parts = []
current = 2
total = 0
while total + current <= n:
parts.append(current)
total += current
current += 1
remaining = n - total
index = len(parts) - 1
while remaining > 0:
parts[index] += 1
remaining -= 1
index -= 1
if index < 0:
index = len(parts) - 1
answer = 1
for value in parts:
answer *= value
print(*parts)
print(answer)cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-27 00:00
* update_at: 2026-07-27 00:00
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXLEN = 200; // 拆出的项数最多约 sqrt(2*10000) ≈ 141
const int BIGLEN = 5000; // 乘积最大位数
int n;
int parts[MAXLEN]; // 拆出的数
int part_cnt;
int big[BIGLEN]; // 大整数数组（逆序）
int big_len;
// 大整数乘法：big[0..big_len-1] *= b
void mul_big(int b) {
int carry = 0;
for (int i = 0; i < big_len; i++) {
int prod = big[i] * b + carry;
big[i] = prod % 10;
carry = prod / 10;
}
while (carry) {
big[big_len++] = carry % 10;
carry /= 10;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
// 贪心拆：从 2 开始尽量取连续数
int cur = 2;
int sum = 0;
while (sum + cur <= n) {
parts[part_cnt++] = cur;
sum += cur;
cur++;
}
// 剩下的数从大到小分散加回去
int remain = n - sum;
int idx = part_cnt - 1;
while (remain > 0) {
parts[idx]++;
remain--;
idx--;
if (idx < 0) idx = part_cnt - 1;
}
// 输出拆分方案
for (int i = 0; i < part_cnt; i++) {
cout << parts[i] << " ";
}
cout << "\n";
// 计算乘积
big[0] = 1;
big_len = 1;
for (int i = 0; i < part_cnt; i++) {
mul_big(parts[i]);
}
// 输出乘积
for (int i = big_len - 1; i >= 0; i--)
cout << big[i];
cout << "\n";
return 0;
}复杂度
拆出的项数约为
总结
本题的核心是贪心拆分：先取尽量多的连续不同数，再把余数分散给较大的项，让整体更均衡。