暴力|最大最小公倍数排序|动态规划

现博客地址：https://www.cnblogs.com/huangzihaoal/p/11154006.html
【题目描述】
已知若干个正整数的和为S，求这若干个正整数的最小公倍数的最大值。
【输入】
第一行一个整数T，表示测试数据的组数。
接下来T行，每行包括一个正整数S，表示若干个正整数的和为S。
【输出】
输出T行，每行包括一个整数，表示和为S的若干个正整数的最小公倍数的最大值。
【样例输入】
2
4
7
【样例输出】
4
12
【暴力|最大最小公倍数】【数据范围限制】
40%的数据：S≤100；
80%的数据：S≤330，结果不会超过long long类型；
100%的数据：2≤S≤500，T≤10，结果不会超过25位整数。
【提示】
样例中第一组数据S=4，它能分解成S=1+1+1+1，S=1+1+2，S=1+3，S=2+2，S=4，很明显S=4时最小公倍数为4，是所有情况中最小公倍数最大的；第二组数据S=7，它能分解成S=3+4，3和4的最小公倍数是12，也是所有情况中最小公倍数最大的。
【题解】
这道题真是害人不浅啊！题目描述那么难懂就算了，还来个高精度！
我比赛时看到题目，哇塞！好难啊！我一直想着怎样把S拆成几个数，并没有找规律（因为最近经常做暴力水法就能过的题）。最后决定使用递归枚举 拆分S的所有情况，再找出最小值更新答案。
结果果然不出我所料，时间超限30！
30分的做法我就不细讲了，毕竟那个并不是正解。
这道题目其实是一道DP！我们可以把S拆分成这个样子：
S = x 1 y 1 + x 2 y 2 + x 3 y 3 + … … x i y i {S=x1^{y1}+x2^{y2}+x3^{y3}+……xi^{yi}} S=x1y1+x2y2+x3y3+……xiyi
其中，x1,x2,x3……,xi均为质数。
那么答案就等于x 1 y 1 ? x 2 y 2 ? x 3 y 3 ? … … ? x i y i {x1^{y1} * x2^{y2} * x3^{y3} * …… * xi^{yi}} x1y1?x2y2?x3y3?……?xiyi（因为质数都是两两互质的，所以不用求它们的最大公因数）
为什么要拆成质数呢？我们可以设A = x 1 y 2 ? x 2 y 2 {A=x1^{y2} * x2^{y2}} A=x1y2?x2y2，但是我们会发现， A > x 1 y 1 + x 2 y 2 {A> x1^{y1}+x2^{y2}} A>x1y1+x2y2，而 A 对答案的贡献却和x 1 y 1 ? x 2 y 2 {x1^{y1} * x2^{y2}} x1y1?x2y2 一样大。也就是说，合数不仅占空间，贡献还质数一样多，所以我们就只用质数，而不用合数了。
下面我们来设状态吧！
我们可以设f[i]为和为i的若干个质数的积的最大值那么我们就可以写出状态转移方程了： f i = m a x ( f i , f i ? x j k ? x j k ) ( 0 ≤ k ≤ i x j ) f_i=max(f_i , f_{i-{x_j}^k} * {x_j}^k ) \quad(0\leq k\leq \frac{i}{x_j}) fi?=max(fi?,fi?xj?k??xj?k)(0≤k≤xj?i?)
其中，j 枚举的是质数，k 枚举的是系数。
额……怎么这题竟然是一道DP？！
温馨提示：

我们可以先算出2~500的所有质数，然后DP，最后读入s（只要立刻输出f[s]就可以了）
DP过程是三重循环的，最外层是j，枚举质数；然后是i，枚举1~500的所有数；最后是k，枚举系数。
记得打高精度！其实我们并不需要打出高精度加、减、乘、除的所有运算，只要打 高精度乘低精度的运算 和 高精度数的判断操作 即可！
DP前记得把f数组直接初始化为1（不然答案都会是0哟）

#include #include #include using namespace std; struct node { int len,a[120]; node() { memset(a,0,sizeof(a)); len=1; } }f[510]; int s[500]; node chengfa_x(node n1,int x)//这里是高精度乘低精度！ { node no; int i; no.len=n1.len; for(i=1; i<=no.len; i++) no.a[i]=n1.a[i]*x; for(i=1; i<=no.len; i++) { no.a[i+1]+=no.a[i]/10; no.a[i]%=10; } i=no.len; while(no.a[i+1]>0) { i++; no.a[i+1]=no.a[i]/10; no.a[i]%=10; } while((no.a[i]==0)&&(i>1)) i--; no.len=i; return no; } bool pd(int k)//判断素数 { int tt=sqrt(k),i; for(i=2; i<=tt; i++) { if(k%i==0) return false; } return true; } node max(node x,node y)//高精度取max值 { if(x.len>y.len) return x; if(x.len=1; i--) { if(x.a[i]>y.a[i]) return x; else if(x.a[i]0; j--)//DP过程 { for(i=500; i>=1; i--) { p=1; for(k=1; k<=8; k++) { p=p*s[j]; if(p>i) break; else { f[i]=max(f[i],chengfa_x(f[i-p],p)); } } } } while(t--) { scanf("%d",&c); for(i=f[c].len; i>=1; i--) printf("%d",f[c].a[i]); printf("\n"); //输入一个，输出一个 } return 0; }