P1249 最大乘積

題目描述

一個正整數一般可以分為幾個互不相同的自然數的和，如 $3=1+2$，$4=1+3$，$5=1+4=2+3$，$6=1+5=2+4$。

現在你的任務是將指定的正整數 $n$ 分解成若干個互不相同的自然數（也可以不分解，就是這個數字本身）的和，且使這些自然數的乘積最大。

輸入格式

只有一個正整數 $n$，（$3\le n\le 10000$）。

輸出格式

第一行是分解方案，相鄰的數之間用一個空格分開，并且按由小到大的順序。

第二行是最大的乘積。

輸入輸出樣例 #1

輸入 #1

10

輸出 #1

2 3 5
30

solution

和一定，求積的最大值，則需要盡量讓乘數(>=2)更多，所以將n分解成2開頭的連續正整數的和，如果有多余的部分 k， 將最后的k個數各加1

代碼

#include <sstream>
#include "iostream"
#include "math.h"using namespace std;
int a[500] = {1};void f(int n) {int s = 0;for (int i = 0; i < 499; i++) {a[i] *= n;a[i] += s;s = a[i] / 10;a[i] %= 10;}
}int main() {int n, k;cin >> n;k = (sqrt(8 * n + 9) - 1) / 2;int nn = (k + 2) * (k - 1) / 2;k++;for (int i = 2; i <= k; i++) {if (i != k - n + nn)cout << i << ' ', f(i);}cout << endl;int j = 499;while (a[j] == 0) j--;for (int i = j; i >= 0; i--) {cout << a[i];}return 0;
}

結果