题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=3092
题意
给出两个数S和M,让你将S分解成多个整数的和,使得这些整数的最小公倍数最大,输出这个最小公倍数(对M取模以后)
题解
- 首先在S的范围内进行素数打表,这样就可以看成取出这么多个素数进行相加的完全背包问题(因为同一个可以取多次,相乘以后照样和其他素数互质)
- 与我们平常见到的完全背包不同的是,如果一个素数取多次,他的代价和收益都是相乘的,而不是相加,所以写法应该在01背包的基础上进行改进,枚举可能相乘的个数
- 因为相乘一定会溢出,同时取模会影响到比较大小,所以采取取对数的方法来对dp数组进行操作,同时另外开一个数组ans[]来记录答案
代码
1 |
|