题目描述
输入描述
一个正整数一般可以分为几个互不相同的自然数的和,如 3=1+2,4=1+3,5=1+4=2+3,6=1+5=2+4。
现在你的任务是将指定的正整数 n 分解成若干个互不相同的自然数的和,且使这些自然数的乘积最大。
输出描述
只一个正整数 n,(3≤n≤10000)。
输入样例
10
输出样例
2 3 5
30
算法
(二分 + 贪心 + 数论 + 高精度)
本题要先用简单的数论和贪心找到最优解的组成方法,再用高精度乘法求积。
以2004为例,由于把2004分拆成若干个互不相等的自然数的和的分法只有有限种,因而一定存在一种分法,使得这些自然数的乘积最大。
若1作因数,则显然乘积不会最大。把2004分拆成若干个互不相等的自然数的和,因数个数越多,乘积越大。为了使因数个数尽可能地多,我们把2004分成2+3…+n直到和大于等于2004。
若和比2004大1,则因数个数至少减少1个,为了使乘积最大,应去掉最小的2,并将最后一个数(最大)加上1。
若和比2004大k(k≠1),则去掉等于k的那个数,便可使乘积最大。//这里用二分查找k值所在位置并删去会更快一些
1.例如15:s=2+3+4+5+6刚好大于15,s-15=5,所以把5去掉。
2.又例如13:s=2+3+4+5刚好大于13,s-13=1,所以去掉2,并把5加1,即3 4 6。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<int> num;
int seek(int x)
{
int l = 0,r = num.size() - 1;
while(l < r)
{
int mid = (l + r) >> 1;
if(x <= num[mid]) r = mid;
else l = mid + 1;
}
return l;
}
vector<int> split_merge(int x)
{
vector<int> S;
while(x){
S.push_back(x % 10);
x /= 10;
}
return S;
}
vector<int> mul(vector<int> &A,vector<int> &B)
{
vector<int> C(A.size() + B.size(), 0);
for (int i = 0; i < A.size(); i++)
for (int j = 0; j < B.size(); j++)
C[i + j] += A[i] * B[j];
int t = 0;
for (int i = 0; i < C.size(); i++){
t += C[i];
C[i] = t % 10;
t /= 10;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
int main()
{
cin >> n;
int sum = 0,i = 2;
while(1){
sum += i;
num.push_back(i ++);
if(sum >= n){
if(sum % n == 1) {*num.end() += 1; num.erase(num.begin());}
else if(sum % n > 1){int p = seek(sum % n); num.erase(num.begin() + p);}
break;
}
}
for(int i = 0;i < num.size();i ++) cout << num[i] << " ";
puts("");
vector<int> C(1,1);
for(int i = 0;i < num.size();i ++)
{
auto A = split_merge(num[i]);auto B = C;
C = mul(A,B);
}
for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
puts("");
return 0;
}