首页 > ACM题库 > HDU-杭电 > HDU 3092-Least common multiple-背包问题-[解题报告]HOJ
2014
03-01

HDU 3092-Least common multiple-背包问题-[解题报告]HOJ

Least common multiple

问题描述 :

Partychen like to do mathematical problems. One day, when he was doing on a least common multiple(LCM) problem, he suddenly thought of a very interesting question: if given a number of S, and we divided S into some numbers , then what is the largest LCM of these numbers? partychen thought this problems for a long time but with no result, so he turned to you for help!
Since the answer can very big,you should give the answer modulo M.

输入:

There are many groups of test case.On each test case only two integers S( 0 < S <= 3000) and M( 2<=M<=10000) as mentioned above.

输出:

There are many groups of test case.On each test case only two integers S( 0 < S <= 3000) and M( 2<=M<=10000) as mentioned above.

样例输入:

6 23

样例输出:

6


Hint: you can divied 6 as 1+2+3 and the LCM(1,2,3)=6 is the largest so we output 6%23=6.

思路:

容易知道,分解成素数的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]了

代码如下:

 

#include<cstdio>
 #include<vector>
 #include<iostream>
 #include<cstring>
 #include<algorithm>
 #include<cmath>
 #define M 10005
 using namespace std;
 double dp[M];
 int p[M];
 int prime[M],cnt,n;
 bool f[M];
 void init()
 {
     cnt=0;
     for(int i=2;i<M;i++){
         if(!f[i]) prime[cnt++]=i;
         for(int j=0;j<cnt&&i*prime[j]<M;j++){
             f[i*prime[j]]=1;
             if(i%prime[j]==0) break;
         }
     }
 }
 void solve(int m)
 {
     memset(dp,0,sizeof(dp));
     for(int i=0;i<=n;i++) p[i]=1;
     for(int i=0;i<cnt&&prime[i]<=n;i++){
         double t=log(prime[i]);
         for(int j=n;j>=prime[i];j--){
             for(int k=prime[i],num=1;k<=j;k*=prime[i],num++)
             if(dp[j-k]+t*num>dp[j]){
                 dp[j]=dp[j-k]+t*num;
                 p[j]=p[j-k]*k%m;
             }
         }
     }
 }
 int main()
 {
     int m;
     init();
     while(scanf("%d%d",&n,&m)!=EOF){
         solve(m);
         printf("%d\n",p[n]);
     }
     return 0;
 }

 

 

 

参考:http://www.cnblogs.com/xin-hua/p/3315197.html


  1. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。