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 }
相关推荐
VanTYS 2019-12-15
数据与算法之美 2014-05-29
ustbfym 2019-11-04
lixiaotao 2019-10-28
ustbfym 2019-10-21
duyifei0 2019-06-28
MachineIntellect 2011-08-28
算法魔功 2018-08-31
程序员生涯 2018-11-08
数据与算法之美 2017-11-27
Wearabledevice 2018-08-26
fengaid 2019-03-18
yhguo00 2017-11-27
卷卷萌 2017-09-02
PHP100 2019-03-28
PHP100 2019-03-28
PHP100 2019-03-28
人生补习班 2018-05-14