最大乘积

题目描述

一个正整数一般可以分为几个互不相同的自然数的和，如 \(3=1+2\)，\(4=1+3\)，\(5＝1+4=2+3\)，\(6=1+5＝2+4\)。

现在你的任务是将指定的正整数 \(n\) 分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大。

输入格式

只一个正整数 \(n\)，（\(3 \leq n \leq 10000\)）。

输出格式

第一行是分解方案，相邻的数之间用一个空格分开，并且按由小到大的顺序。

第二行是最大的乘积。

样例 #1

样例输入 #1

样例输出 #1

2 3 5
30

题解

思路

按照贪心的思路来说，尽量不要出现1才使得乘积最大，然后总和是n，就从2开始遍历，一直到分解不动的情况，会出现余数不等于0的情况。

把余数分到大的数上比分到小的数上得到的乘积更大

处理余数有两种情况

余数是加1到所有分解方案刚好或者足够
余数是加1到所有分解方案还有剩余，这样的情况直接所有剩余的加到分解方案最后的一个值上

最后就涉及到一个大数相乘的方法，把所有的分解结果依次相乘即可

code

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define SZ(v) ((int)v.size())
#define pii pair<int, int>
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef double db;
using namespace std;
const int N = 1e6+10;
int _;
int n;
int ans[N];
string s[N];
string res;
int len;

string f(string a) {
    for(int i = 0; i < SZ(a) / 2; i++) {
        swap(a[i], a[SZ(a)-i-1]);
    }
    return a;
}

string add(string a, string b) {
    int len1 = SZ(a), len2 = SZ(b);
    vector<int> c(max(len1, len2), 0), d(max(len1, len2), 0);
    for(int i = 0; i < len1; i++) c[i] = a[i] - '0';
    for(int i = 0; i < len2; i++) d[i] = b[i] - '0';
    int k = 0;
    string ans = "";
    for(int i = 0; i < max(len1, len2); i++) {
        int x = c[i] + d[i] + k;
        k = x / 10;
        ans += to_string(x%10);
    }
    if(k) ans += to_string(k);
    return ans;
}

string mul(string a, string b) {
    int len1 = SZ(a), len2 = SZ(b);
    vector<int> c(max(len1, len2), 0), d(max(len1, len2), 0);
    for(int i = 0; i < len1; i++) c[i] = a[i] - '0';
    for(int i = 0; i < len2; i++) d[i] = b[i] - '0';
    string ans = "";
    for(int i = 0; i < len1; i++) {
        string tmp = "";
        for(int j = 0; j < i; j++) tmp += "0";
        int k = 0;
        for(int j = 0; j < len2; j++) {
            int x = c[i] * d[j] + k;
            k = x / 10;
            tmp += to_string(x % 10);
        }
        if(k) tmp += to_string(k);
        ans = add(ans, tmp);
    }
    return ans;
}

void solve() {
    cin >> n;
    for(int i = 2; i <= n; i++) {
        if(i <= n) {
            ans[len] = i;
            s[len] = f(to_string(i));
            len++; 
            n -= i;
        }
    }
    for(int i = len - 1; i >= 0; i--) {
        if(n > 0) {
            ans[i] += 1;
            s[i] = f(to_string(ans[i]));
            n--;
        }
    }
    if(n > 0) {
        ans[len-1] += n;
        s[len-1] = f(to_string(ans[len-1]));
    }
    for(int i = 0; i < len; i++) {
        cout << ans[i] << " ";
    }
    res = s[0];
    for(int i = 1; i < len; i++) {
        res = mul(res, s[i]);
    }
    cout << "\n";
    for(int i = SZ(res) - 1; i >= 0; i--) {
        cout << res[i];
    }
    cout << "\n";
}   

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
    _ = 1;
    // freopen('')
    // cin >> _;
    while(_--) {
        solve();
    }
    return 0;
}