一、问题描述
设 n 是一个正整数。现在要求将 n 分解为若干个自然数之和，使得自然数的成绩最大。输出这个最大的乘积。
要求
（1）要求这些自然数 互不相同。
（2）要求这些自然数 可以相同。（同一个数结果大于等于（1）的结果）
二、问题分析
1、要求这些自然数 互不相同
先来看几个数找找规律
（1）小于等于 4 的情况就不用说了。
（2）从 5 开始写起：5=2+3，6=2+4，7=3+4，8=3+5，9=2+3+4，10=2+3+5，11=2+4+5
Ps：从 1 开始写没意义，因为相乘还是 1*x==x 还少了相对于原来的 n 还少了 1 呢，更小了，所以从 2 开始才行~
发现规律如下
尽量使得元素是连续的，（一律从 2 开始）。
如果连续加的时候，某个数 k 加的时候正好超出了 n ，则该数 k 不能算入，而是把让 rest =（n - 前面 ( k - 1 ) 项总和），从后往前（因为一开始就使升序，所以也从大到小）均匀分配（+1）到各个元素，直到 rest == 0。
Code
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; int a[100],b[100]; int main() { int rs=0,len=0; for(int i=2;rs<=1100;i++) { a[len++]=i; rs+=i; } int n; while(~scanf("%d",&n)) { if(n<=4) // 没办法拆分成不同的数使乘积大于等于 (1*n) { //... continue; } rs=0; int k=0; for(int i=0;i<len-1;i++) { rs+=a[i]; if(n-rs<a[i+1]) { b[k++]=a[i]; rs=n-rs; int j=k-1; while(1) { b[j--]+=1; rs--; if(rs<=0) break; if(j==-1) j=k-1; } break; } else if(n-rs==a[i+1]) { b[k++]=a[i]; b[k++]=a[i+1]; break; } else b[k++]=a[i]; if(rs<=0) break; } printf("%d",b[0]); for(int i=1;i<k;i++) printf(" %d",b[i]); puts(""); } return 0; }
2、要求这些自然数 可以相同
先来看几个数找找规律：4=2+2，5=2+3，6=3+3，7=3+2+2，8=3+3+2，9=3+3+3
发现规律如下
（1）元素不会超过4，因为4=2+2，又可以转化为2的问题，而5=2+3，5<2*3，所以5总能分解成2和3。
（2）尽可能多分解出3，然后分解出2，不要分出1。
考虑任意一个数，除以3之后的结果有以下3种
（1）能被3除断（即整除），那么就分解为3+3+...+3的情况即可。例如：9=3+3+3。
（2）被3除余1，分解为3+3+...+3+2+2或者3+3+...+3+4的情况，例如：10=3+3+2+2
（3）被3除余2，分解为3+3+...+3+2的情况，例如：11=3+3+3+2。
Code（注意：有秒杀公式）
/
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; int main() { int T; scanf("%d",&T); int n; while(T-- && ~scanf("%d",&n)) { int rs; if(n==0) rs=1; // 根据题目需要 else if(n<4) rs=n; // 根据题目需要 else { int cnt3,cnt2; // 3的个数 2的个数 if(n%2==1) // 奇数时 { cnt3=(n-3)/6*2+1; cnt2=(n-3)%6/2; } else // 偶数时 { cnt3=n/6; cnt2=n%6/2; } rs=pow(3,cnt3) * pow(2,cnt2); } printf("%d\n",rs); } return 0; }
