题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3092
给你一个数n，它可以被切割成许多整数的和，比如6=1+2+3，这些数字在一起有一个最小公倍数LCM。现在要我们求出切割成整数可以的到的最大的最小公倍数。
要想切割之后得到最大的最小公倍数，那么切割的数字之间最好就是两两互质，每两个数字的最小公倍数就是a*b/gcd(a,b)，当a，b互质的时候，gcd(a,b)==1。所以我们就可以把1到3000里面的素数筛出来，然后看n里面可以包含哪些素数，比如9=2+2+5，所以最大的值就是2^2*5=20。对于一个素数我们拿的是它小于等于容量时的最大次方数。于是就可以转化为01背包。
但是我wa了好多次，这里有个注意的地方就是答案是最大LCM对m取模的值，不可以边计算边取模，这样会导致答案错误，但是用基本数据类型会溢出啊，但是在再一次看别人博客之后不得不说人的脑洞是真的大。我们可以用dp数组来储存LCM的对数，就是log（LCM），然后用另一个数组ans来存储LCM对m取模的值，这样就可以得到正确的结果。
公式就是log(a*b)=log(a)+log(b)，log(a^c)=clog(a)。
具体可以看代码：
#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<map> #include<stack> #include<cmath> #include<vector> #include<set> #include<cstdio> #include<string> #include<deque> using namespace std; typedef long long LL; #define eps 1e-8 #define INF 0x3f3f3f3f #define maxn 3005 /*struct point{ int u,w; }; bool operator <(const point &s1,const point &s2) { if(s1.w!=s2.w) return s1.w>s2.w; else return s1.u>s2.u; }*/ double dp[maxn]; int n,m,k,t,cnt; int prime[maxn]; bool vis[maxn]; int ans[maxn]; void init() { cnt=0; memset(vis,false,sizeof(vis)); for(int i=2;i<maxn;i++){ if(!vis[i]) { prime[++cnt]=i; for(int j=2*i;j<=maxn;j+=i){ vis[j]=true; } } } } int main() { init(); while(scanf("%d%d",&n,&m)!=EOF) { memset(dp,0,sizeof(dp)); fill(ans,ans+maxn-1,1); for(int i=1;i<=cnt&&prime[i]<=n;i++){//枚举素数 double lo=log10(prime[i]*1.0);//求素数的对数 for(int j=n;j>=prime[i];j--){//对于素数的倍数，只能拿一次，所以逆序 for(int num=1,k=prime[i];k<=j;k*=prime[i],num++){// log(a*b)=log(a)+log(b) log(a^c)=clog(a) if(dp[j]<dp[j-k]+lo*num) { dp[j]=dp[j-k]+lo*num;//dp存最大LCM的对数 ans[j]=(ans[j-k]*k)%m;//ans存最大LCM对m取模的值 } } } } printf("%d ",ans[n]); } return 0; }