【题目来源】
洛谷：P1249 最大乘积 - 洛谷 (luogu.com.cn)
【题目描述】
一个正整数一般可以分为几个互不相同的自然数的和，如 \(3=1+2\)，\(4=1+3\)，\(5＝1+4=2+3\)，\(6=1+5＝2+4\)。
现在你的任务是将指定的正整数 \(n\) 分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大。
【输入】
只一个正整数 \(n\)，（\(3\le n\le 10000\)）。
【输出】
第一行是分解方案，相邻的数之间用一个空格分开，并且按由小到大的顺序。
第二行是最大的乘积。
【输入样例】
10
【输出样例】
2 3 5
30
【算法标签】
《洛谷 P1249 最大乘积》 #贪心# #高精度#
【代码详解】
#include<iostream>
#include<algorithm>
using namespace std;const int L = 500; // 定义高精度计算的最大位数// 高精度乘法函数：计算两个字符串表示的大整数的乘积
string mul(string a, string b)
{string s; // 存储结果int na[L], nb[L], nc[L]; // na, nb 存储两个乘数的每一位，nc 存储乘积的每一位int La = a.size(), Lb = b.size(); // La 和 Lb 分别是两个乘数的长度fill(na, na + L, 0); // 初始化 na 数组为 0fill(nb, nb + L, 0); // 初始化 nb 数组为 0fill(nc, nc + L, 0); // 初始化 nc 数组为 0// 将字符串 a 转换为整数数组 na（逆序存储）for (int i = La - 1; i >= 0; i--) na[La - i] = a[i] - '0';// 将字符串 b 转换为整数数组 nb（逆序存储）for (int i = Lb - 1; i >= 0; i--) nb[Lb - i] = b[i] - '0';// 高精度乘法核心计算for (int i = 1; i <= La; i++) for (int j = 1; j <= Lb; j++) nc[i + j - 1] += na[i] * nb[j]; // 逐位相乘并累加到结果数组// 处理进位for (int i = 1; i <= La + Lb; i++) {nc[i + 1] += nc[i] / 10; // 进位nc[i] %= 10; // 取个位数}// 将结果数组转换为字符串if (nc[La + Lb]) s += nc[La + Lb] + '0'; // 如果最高位不为 0，添加到结果for (int i = La + Lb - 1; i >= 1; i--) s += nc[i] + '0'; // 从高位到低位依次添加return s; // 返回结果字符串
}// 将整数转换为字符串
string f(int a)
{char ch[10], t; // ch 用于存储字符形式的数字int i = 0;int j;// 将整数 a 转换为字符数组（逆序）while (a) {ch[i] = a % 10 + '0'; // 取个位数并转换为字符a /= 10; // 去掉个位数i++;}ch[i] = '\0'; // 添加字符串结束符// 将字符数组倒序，得到正确的字符串for (i = i - 1, j = 0; j <= i / 2; j++, i--) {t = ch[i];ch[i] = ch[j];ch[j] = t;}return ch; // 返回字符串
}int n, a[1005]; // n 是输入的整数，a 数组存储拆分后的整数
string s[1005]; // s 数组存储拆分后的整数的字符串形式
int c = 1; // c 记录拆分后的整数个数int main()
{string m = "1"; // m 用于存储乘积结果，初始值为 1// 输入cin >> n;// 特判：如果 n 小于等于 4，直接输出 n 和 nif (n <= 4) {cout << n << endl << n;return 0;}// 拆项：将 n 拆分为若干个整数，使得这些整数的乘积最大for (int i = 2; i <= n; i++) {if (n >= i) {n -= i; // 从 n 中减去 ia[c++] = i; // 将 i 存入 a 数组s[c - 1] = f(i); // 将 i 转换为字符串并存入 s 数组} else break; // 如果 n 不足以减去 i，退出循环}// 如果有余数，从最高位开始加一for (int i = c - 1; i >= 1; i--) {if (n > 0) {a[i]++; // 当前位加一s[i] = f(a[i]); // 更新字符串形式n--; // 余数减一}}// 如果还有余数，让最后一个数加一if (n > 0) {a[c - 1]++;s[c - 1] = f(a[c - 1]);}// 高精度乘法计算拆分后的整数的乘积for (int i = 1; i < c; i++) {cout << a[i] << " "; // 输出拆分后的整数m = mul(s[i], m); // 计算乘积}// 输出结果cout << endl << m;return 0;
}
【运行结果】
10
2 3 5
30