P1249 最大乘积

题目传送门

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
/**
 这道题本蒟蒻直接开始无脑找规律，一小时之后终于找出来了，打完发现高精忘了。。。
很明显就知道1在分解中没有任何作用，所以不会分1；
举个例子吧9=2+3+4；很明显2 3 4便是最优解；
2 3 4 5是14的最优解； 于是就开始了艰辛的找规律之路：
5：2 3
6：2 4
7：3 4
8：3 5
9：2 3 4
10：2 3 5
11：2 4 5
12：3 4 5
13：3 4 6
14：2 3 4 5； 到这里规律就很明显了：
在两个阶乘数之间循环：
举个栗子： 5的最优解是2 3，6比5大1，前面已经说过1是浪费的，所以在2和3之间选一个数加1； 一般规律如下：
设x1=2+3+4+....+n;x2=2+3+4+....+n+n+1;
从x1往后的数的最优解为从该序列末尾依次加1；仔细研究↑的列举；
加完后还剩一个x2-1这个数，这个数的序列便是x2-2的序列的最后一项再加上1；原谅本蒟蒻，这规律实在是太难解释了；
 */
//高精度乘法模板
vector<int> mul(vector<int> &A, int b) {
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || t; i++) {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int n, num;
int ans;
vector<int> C;

int main() {
    cin >> n;
    //无脑的增大序列
    for (num = 2;; num++) {
        if (ans + num > n) break;
        ans += num;
        C.push_back(num);
    }
    //如果还有剩余
    int r = n - ans;

    //后面的人，每人一个
    for (int i = 0; i < r; i++) C[C.size() - 1 - i]++;

    //输出C
    for (int i = 0; i < C.size(); i++) printf("%d ", C[i]);
    printf("\n");

    //下面是高精度乘法
    vector<int> A;
    A.push_back(1);
    for (int i = 0; i < C.size(); i++) A = mul(A, C[i]);

    //倒着输出
    for (int i = A.size() - 1; i >= 0; i--) printf("%d", A[i]);
    return 0;
}