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

发表于 | 分类于 | 阅读次数:
字数统计: 556 字

题目链接： 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;
}