巧拆正整数：求最大乘积数字之和的算法揭秘

问题分析 将正整数 \( X \) 拆分成若干个互不相同的正整数，使它们的和等于 \( X \)，且乘积最大。 目标：输出这个最大乘积的数字之和（不是乘积本身）。 --- 关键思路 1. 拆分原则 - 数字互不相同。 - 从最小的正整数开始选（1, 2, 3, …），直到剩余值小于下一个可选数时，将剩余值加到最后一个数上（或调整最后几个数，使数字仍互不相同且乘积最大）。 - 经验规律：最优拆分是连续自然数（或接近连续），且尽量不出现 1（因为 1 对乘积无贡献，除非必须）。 2. 例子分析 \( X = 9 \)： 尝试连续自然数： \( 2 + 3 + 4 = 9 \)，乘积 \( 2 \times 3 \times 4 = 24 \)（最大）。 数字之和 \( 2 + 3 + 4 = 9 \)？不对，题目要求输出“最大乘积的数字之和”，这里乘积是 24，数字之和是 9，但样例输出是 6。 仔细看样例： 样例输入 9，输出 6。 6 是 \( 2 + 3 + 4 \) 的数字之和吗？不是，那是 9。 所以这里“最大乘积的数字之和”是指 乘积的各位数字之和，不是拆分出的数字之和。 验证：乘积 24，各位数字 2 + 4 = 6，符合样例输出。 3. 结论 题目要求： - 找到拆分方式使乘积最大。 - 计算这个最大乘积。 - 输出该乘积的各位数字之和。 --- 算法步骤 1. 从 2 开始累加连续自然数，直到和超过 \( X \) 为止，然后调整最后一个数使和等于 \( X \)，且数字互不相同。 2. 调整方法： - 设拆分为 \( a_1, a_2, \dots, a_k \)（递增连续自然数），和 \( S = \sum a_i \)。 - 若 \( S > X \)，则去掉某个数并调整。 - 更优方法：从 2 开始连续取，直到剩余值小于下一个数时，将剩余值加到最后一个数上（但要检查是否与前面重复）。 - 更稳定方法：先拆成连续自然数 2, 3, …, m，使得和 \( \le X \)，剩余 \( r = X - \sum_{i=2}^m i \)。 如果 \( r > 0 \)，则从最大数开始依次加 1，直到 r 用完，确保不重复。 3. 计算乘积（可能很大，用高精度）。 4. 计算乘积的各位数字之和。 --- 举例 \( X = 9 \)： 从 2 开始：2 + 3 + 4 = 9，刚好。 乘积 = 24，数字和 = 2 + 4 = 6。 \( X = 10 \)： 2 + 3 + 4 = 9，剩 1，加到 4 上得 5 → 2, 3, 5，乘积 30，数字和 3 + 0 = 3。 --- 代码实现（Python） ```python def max_product_split(X): # 1. 构造最优拆分列表 parts = [] next_num = 2 remaining = X while remaining >= next_num: parts.append(next_num) remaining -= next_num next_num += 1 # 剩余值加到已有的部分（从后往前加，避免重复） idx = len(parts) - 1 while remaining > 0: parts[idx] += 1 remaining -= 1 idx -= 1 if idx < 0: idx = len(parts) - 1 # 2. 计算乘积（高精度） from math import prod product = prod(parts) # 3. 计算乘积的数字之和 digit_sum = sum(int(d) for d in str(product)) return digit_sum # 输入输出 N = int(input().strip()) print(max_product_split(N)) ``` --- 样例验证 输入： ``` 9 ``` 输出： ``` 6 ``` 符合题意。 ######[AI问答 | 998点数解答 | 2026-01-11 13:35:48]