P1249 最大乘积

乘积"/>

P1249 最大乘积

难度：3

这道题的答案输出需要高精度，但是思路确是贪心以及数学，题目的问题是，把一个数分成若干个不同的数，怎么分乘积最大，这里就是尽量分的个数越多越好，而且1显然是没有用的，然后就从2开始累加，接下来会出现三种情况，

第一是恰好累加到了目标数字，那么就把这个作为答案输出，第二是大于目标数字，当前累加和与目标数字的差大于1，那么就直接把这个差值去掉就行了，因为是从2开始连续连续累加的，所以这个差值一开始一定作为因子放进来了，第三是大于目标数字，当前累加和与目标数字的差等于1，那么把2去掉，然后把因子最后一个数字加1放进来作为新的因子，这种情况下，得到的乘积一定是最大的，

#include <bits/stdc++.h>#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()using namespace std;typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pa;const int maxn = 5005;struct Bigint {int len, a[maxn];Bigint(int x = 0) {memset(a, 0, sizeof(a));len = 1;while (x) {a[len++] = x % 10;x /= 10;}len--;}int &operator[](int i) {return a[i];}void flatten(int l) {len = l;for (int i = 1; i <= len; i++) {a[i + 1] += a[i] / 10;a[i] %= 10;}while (a[len] == 0) len--;}void print() {for (int i = max(1, len); i >= 1; i--) {cout << a[i];}}
};Bigint operator*(Bigint a, Bigint b) {Bigint c;for (int i = 1; i <= a.len; i++) {for (int j = 1; j <= b.len; j++) {c[i + j - 1] += a[i] * b[j];}}c.flatten(a.len + b.len);return c;
}int Hash[100005];int main() {int n;cin >> n;int tmp = 0;Bigint ans(1);for (int i = 2; i <= n; i++) {Hash[i] = 1;tmp += i;if (tmp == n) {for (int j = 2; j <= n; j++) {if (Hash[j]) {Bigint fac(j);ans = ans * fac;}}break;} else if (tmp > n) {if (tmp - n > 1) Hash[tmp - n] = 0;else Hash[2] = 0, Hash[i + 1] = 1;for (int j = 2; j <= n; j++) {if (Hash[j]) {Bigint fac(j);ans = ans * fac;}}break;}}for (int i = 2; i <= n; i++) {if (Hash[i]) cout << i << " ";}cout << endl;ans.print();return 0;
}