HDU-3092 Least common multiple---数论+分组背包

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=3092

题目大意：

有一个数字n，现在要把它分解成几个数字相加！然后这几个数字有最小公倍数，题目目的是求出最大的最小公倍数。我们知道所有的素数或者其指数方相加可以表示其它的数字，而把n分解之后求其公倍数自然是互质的数字直接相乘最大，所以目的就变成了求n能分解之后由素数或者其指数数，只要他们之间相互互质就行。

解题思路：

将n分解成不同素数之和，这样就是两两互质，求出的lcm是最大的，而且不只是素数之和，可以分解成素数的k次方，这样不同的素数的k次方之间仍然是互质的。

这样变成了分组背包，每一个素数就是一组，这一组中只能选一个，而背包容量为S。求出最大的价值即可。

还有一个问题，由于价值过大，需要取模，但是随便取模的话就不好判断大小，所以采用取对数的方法，一个数组记录取对数的值，一个数据记录答案，每次按照取对数的数组的大小判断是否需要更新，需要更新的话直接更新该数组和答案数组。

1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll n, m;
 5 const int maxn = 3000 + 10;
 6 bool is_prime[maxn];
 7 ll prime[maxn], tot, ans[maxn];
 8 double dp[maxn];
 9 void init(int n)
10 {
11     for(int i = 2; i <= n; i++)is_prime[i] = 1;
12     for(int i = 2; i <= n; i++)
13         if(is_prime[i])
14         {
15             prime[tot++] = i;
16             for(int j = i * 2; j <= n; j += i)is_prime[j] = 0;
17         }
18     //for(int i = 0; i < tot; i++)cout<<prime[i]<<endl;
19 }
20 int main()
21 {
22     init(3000);
23     while(cin >> n >> m)
24     {
25         for(int i = 0; i <= n; i++)dp[i] = 0, ans[i] = 1;
26         for(int i = 0; i < tot && prime[i] <= n; i++)
27         {
28             double tmp = log(prime[i]);
29             for(int j = n; j >= 1; j--)
30             {
31                 ll k = prime[i], cnt = 1;
32                 while(k <= j)
33                 {
34                     if(dp[j] < dp[j - k] + tmp * cnt)
35                     {
36                         dp[j] = dp[j - k] + tmp * cnt;
37                         ans[j] = ans[j - k] * k % m;
38                     }
39                     cnt++;
40                     k *= prime[i];
41                 }
42             }
43         //for(int i = 1; i <= n; i++)cout<<dp[i]<<endl;
44         }
45         cout<<ans[n]<<endl;
46     }
47     return 0;
48 }