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.
【题意】给你一个数N和结果的mod M。求如何划分N，使得子集和为N的集合的LCM最大。
从数学上来看，lcm(a, b) = a/gcd(a, b)*b, 只有在gcd(a, b)为1的时候，lcm最大，也就是分割的集合里的每一个数都是互质的。
每个质数和它的幂次作为分组背包的一组（因为每个数互质的时候，lcm最大）；由于dp的时候取模会导致dp结果不正确，而不取模又会导致dp结果过大。由对数的单调性，和对数加法和乘法的性质，dp[i]为i的对数的分割的最大lcm。同时需要另一个数组保留最后结果。
代码如下：
1 #include <iostream> 2 #include <cmath> 3 #include <cstring> 4 #include <algorithm> 5 #include <cstdio> 6 using namespace std; 7 #define ll long long 8 9 int prime[3100], pri_size = 0; 10 bool isprime[3100]; 11 void sieve(int num) 12 { 13 memset(prime, 0, sizeof(prime)); 14 memset(isprime, true, sizeof(isprime)); 15 isprime[0] = isprime[1] = false; 16 for(int i = 2; i <= num; i++ ) { 17 if(isprime[i]) { 18 prime[pri_size++] = i; 19 // cout << i << " "; 20 } 21 for(int j = 0; i*prime[j] <= num; j++){ 22 isprime[i*prime[j]] = false; 23 if(i%prime[j] == 0) break; 24 } 25 } 26 // cout << endl; 27 } 28 int main() 29 { 30 int n, m; 31 sieve(3000); 32 while(cin >> n >> m) { 33 int ans[3100]; 34 double dp[3100]; 35 for(int i = 0; i <= n; i++ ) {dp[i] = 0; ans[i] = 1;} 36 37 for(int i = 0; i < pri_size && prime[i] <= n; i++) { 38 double log_p = log(prime[i]); 39 for(int j = n; j >= 1; j--) { 40 ll pri = prime[i], cnt = 1; 41 while(pri <= j) { 42 if(dp[j] < dp[j-pri] + log_p*cnt) { 43 dp[j] = dp[j-pri] + log_p * cnt; 44 ans[j] = ans[j-pri] * pri % m; 45 } 46 cnt++; 47 pri *= prime[i]; 48 } 49 } 50 } 51 cout << ans[n] << endl; 52 } 53 }