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 }
浙公網安備 33010602011771號