题目描述
一个正整数一般可以分为几个互不相同的自然数的和，如 3=1+2,4=1+35,＝1+4=2+3,6=1+5＝2+4。现在你的任务是将指定的正整数 nn 分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大。
输入格式 只一个正整数 n，（3≤n≤10000）。
输出格式第一行是分解方案，相邻的数之间用一个空格分开，并且按由小到大的顺序。第二行是最大的乘积。
输入输出样例
输入
10
输出
2 3 5
30
#include <iostream> #include <cmath> #include <cstring> using namespace std; typedef long long ll; int n,a[1000],t; struct bn{ int len; int d[10000]; bn() { memset(d, 0, sizeof(d)); len = 0; } }; bn mul(bn a, int b) { int carry = 0; bign res; for(int i = 0; i < a.len; i++) { int tem = a.d[i] * b + carry; res.d[res.len++] = tem % 10; carry = tem / 10; } while(carry) { res.d[res.len++] = carry % 10; carry /= 10; } while(res.len > 1 && res.d[res.len - 1] == 0) res.len--; return res; } void output(bn ans) { for(int i = ans.len - 1; i >= 0; i--) cout << ans.d[i]; cout << endl; } int main() { cin >> n; if(n < 5) { cout << n; return 0; } int id = 2, sum = 0; while(n) { a[t++] = id; sum += id++; if(sum == n) break; if(sum > n) { if(sum == n + 1) { a[0] = 1; a[t - 1]++; } else { for(int i = 0; i < t; i++) if(a[i] == sum - n) { a[i] = 1; break; } } break; } } bn ans; ans.len = 1; ans.d[0] = 1; for(int i = 0; i < t; i++) { if(a[i] != 1) cout << a[i] << " "; } cout << endl; for(int i = 0; i < t; i++) { ans = mul(ans, a[i]); } output(ans); return 0; }
