思路:
容易知道,分解成素数的lcm肯定是最大的,因为假设分解成2个合数,设定x为他们的 最大公约数,
那么他们的最小公倍数就要减少x倍了
然后如果是素数之间的最小公倍数,那么就只是他们的乘积,同样的n分解,没有 除的肯定比有除的大,
因此可以得到结论 所以可以先晒一次素数,然后用这些素数填满那个n
这里填满也很容易想到是背包问题了,因为同一个素数可以用几次,所以就是一个 典型的多重背包了,
就是dp[j] = lcm(dp[j - k] , dp[k]);
然后还有一个问题,就是对于所有素数取lcm,会导致结果很大,超int的 而且虽然有取mod,
那么转移方程变为dp[j] = dp[j - k] * w * prime[i]; 都是乘法运算,那么我们就可以利用取对数,
把乘法运算转成加法来判断了就行了 然后另开一个数组,用来取mod的,最后结果就是dp[n]了
代码如下:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<cstdio> 2 #include<vector> 3 #include<iostream> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #define M 10005 8 using namespace std; 9 double dp[M]; 10 int p[M]; 11 int prime[M],cnt,n; 12 bool f[M]; 13 void init() 14 { 15 cnt=0; 16 for(int i=2;i<M;i++){ 17 if(!f[i]) prime[cnt++]=i; 18 for(int j=0;j<cnt&&i*prime[j]<M;j++){ 19 f[i*prime[j]]=1; 20 if(i%prime[j]==0) break; 21 } 22 } 23 } 24 void solve(int m) 25 { 26 memset(dp,0,sizeof(dp)); 27 for(int i=0;i<=n;i++) p[i]=1; 28 for(int i=0;i<cnt&&prime[i]<=n;i++){ 29 double t=log(prime[i]); 30 for(int j=n;j>=prime[i];j--){ 31 for(int k=prime[i],num=1;k<=j;k*=prime[i],num++) 32 if(dp[j-k]+t*num>dp[j]){ 33 dp[j]=dp[j-k]+t*num; 34 p[j]=p[j-k]*k%m; 35 } 36 } 37 } 38 } 39 int main() 40 { 41 int m; 42 init(); 43 while(scanf("%d%d",&n,&m)!=EOF){ 44 solve(m); 45 printf("%d ",p[n]); 46 } 47 return 0; 48 }