HDU 3092 Least common multiple 素数打表+ 完全背包

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=3092

题意

给出两个数S和M,让你将S分解成多个整数的和,使得这些整数的最小公倍数最大,输出这个最小公倍数(对M取模以后)

题解

  • 首先在S的范围内进行素数打表,这样就可以看成取出这么多个素数进行相加的完全背包问题(因为同一个可以取多次,相乘以后照样和其他素数互质)
  • 与我们平常见到的完全背包不同的是,如果一个素数取多次,他的代价和收益都是相乘的,而不是相加,所以写法应该在01背包的基础上进行改进,枚举可能相乘的个数
  • 因为相乘一定会溢出,同时取模会影响到比较大小,所以采取取对数的方法来对dp数组进行操作,同时另外开一个数组ans[]来记录答案

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<iostream>
#include<queue>
#include<set>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
const int mod=1e9+7;
const int maxn=3005;
const int maxm=10005;
bool is_prime[maxn];
int prime[maxn],num;
double dp[maxn];
ll ans[maxn];
void prime_init()
{
num=0;
memset(is_prime,true,sizeof(is_prime));
is_prime[0]=is_prime[1]=false;
for(int i=2;i<maxn;i++)
{
if(is_prime[i])prime[num++]=i;
for(int j=0;j<num && i*prime[j]<maxn;j++)
{
is_prime[i*prime[j]]=false;
if(i%prime[j]==0)break; //保证每一个合数都被他的最小质因数排除
}
}
}
void solve()
{
int S,M;
prime_init();
while(scanf("%d %d",&S,&M)!=EOF)
{
memset(dp,0,sizeof(dp));
fill(ans,ans+num,1);
for(int i=0;i<num && prime[i]<S ;i++)
{
double tmp=log(prime[i]*1.0);
for(ll j=S;j>=prime[i];j--)
for(ll k=prime[i],q=1;k<=j;k*=prime[i],q++) //可以重复,q表示重复次数
if(dp[j-k]+q*tmp>dp[j])
{
dp[j]=dp[j-k]+q*tmp;
ans[j]=ans[j-k]*k%M;
}
}
printf("%lld\n",ans[S]);
}
}
int main()
{
freopen("input.txt","r",stdin);
solve();
return 0;
}