HDU-3092 Least common multiple---数论+分组背包
2024-09-02 03:39:44
题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=3092
题目大意:
有一个数字n,现在要把它分解成几个数字相加!然后这几个数字有最小公倍数,题目目的是求出最大的最小公倍数。我们知道所有的素数或者其指数方相加可以表示其它的数字,而把n分解之后求其公倍数自然是互质的数字直接相乘最大,所以目的就变成了求n能分解之后由素数或者其指数数,只要他们之间相互互质就行。
解题思路:
将n分解成不同素数之和,这样就是两两互质,求出的lcm是最大的,而且不只是素数之和,可以分解成素数的k次方,这样不同的素数的k次方之间仍然是互质的。
这样变成了分组背包,每一个素数就是一组,这一组中只能选一个,而背包容量为S。求出最大的价值即可。
还有一个问题,由于价值过大,需要取模,但是随便取模的话就不好判断大小,所以采用取对数的方法,一个数组记录取对数的值,一个数据记录答案,每次按照取对数的数组的大小判断是否需要更新,需要更新的话直接更新该数组和答案数组。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m;
const int maxn = + ;
bool is_prime[maxn];
ll prime[maxn], tot, ans[maxn];
double dp[maxn];
void init(int n)
{
for(int i = ; i <= n; i++)is_prime[i] = ;
for(int i = ; i <= n; i++)
if(is_prime[i])
{
prime[tot++] = i;
for(int j = i * ; j <= n; j += i)is_prime[j] = ;
}
//for(int i = 0; i < tot; i++)cout<<prime[i]<<endl;
}
int main()
{
init();
while(cin >> n >> m)
{
for(int i = ; i <= n; i++)dp[i] = , ans[i] = ;
for(int i = ; i < tot && prime[i] <= n; i++)
{
double tmp = log(prime[i]);
for(int j = n; j >= ; j--)
{
ll k = prime[i], cnt = ;
while(k <= j)
{
if(dp[j] < dp[j - k] + tmp * cnt)
{
dp[j] = dp[j - k] + tmp * cnt;
ans[j] = ans[j - k] * k % m;
}
cnt++;
k *= prime[i];
}
}
//for(int i = 1; i <= n; i++)cout<<dp[i]<<endl;
}
cout<<ans[n]<<endl;
}
return ;
}
最新文章
- 小小C程序(九九乘法表)
- wampserver的安装以及使用
- Djanog结合jquery实现ajax
- a* products
- Java -- File
- H5元素
- CSS的引入方式
- 【经验】angularjs 实现带查找筛选功能的select下拉框
- UVA 11754 Code Feat 中国剩余定理+暴力
- java之Comparator与Comparable
- Python多进程使用
- paip.输入法编程---增加码表类型
- python:利用asyncio进行快速抓取
- Libcurl细说
- Subscription wildcards(MQTT)
- Go解析写死的json
- [Swift]LeetCode968.监控二叉树 | Binary Tree Cameras
- ES(Elasticsearch)
- SQL Server-常用分页语句
- Spring xml配置
热门文章
- zabbix web url监控
- (转)[Nginx] – 配置文件优化 [一 ,二]
- 抓包来看ftp状态码
- (Frontend Newbie)JavaScript基础之常见数据类型
- springboot整合activeMq 跳坑
- Java Bean Validation(参数校验) 最佳实践
- [转]ASP.NET MVC中的两个Action之间值的传递--TempData
- Javascript 5种设计风格
- C#基础(第一天)
- 从零开始写C# MVC框架之--- 配置log4日志