hdu 3092 Least common multiple
2024-10-16 23:42:37
思路:
容易知道,分解成素数的lcm肯定是最大的,因为假设分解成2个合数,设定x为他们的 最大公约数,
那么他们的最小公倍数就要减少x倍了
然后如果是素数之间的最小公倍数,那么就只是他们的乘积,同样的n分解,没有 除的肯定比有除的大,
因此可以得到结论 所以可以先晒一次素数,然后用这些素数填满那个n
这里填满也很容易想到是背包问题了,因为同一个素数可以用几次,所以就是一个 典型的多重背包了,
就是dp[j] = lcm(dp[j - k] , dp[k]);
然后还有一个问题,就是对于所有素数取lcm,会导致结果很大,超int的 而且虽然有取mod,
那么转移方程变为dp[j] = dp[j - k] * w * prime[i]; 都是乘法运算,那么我们就可以利用取对数,
把乘法运算转成加法来判断了就行了 然后另开一个数组,用来取mod的,最后结果就是dp[n]了
代码如下:
#include<cstdio>
#include<vector>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define M 10005
using namespace std;
double dp[M];
int p[M];
int prime[M],cnt,n;
bool f[M];
void init()
{
cnt=;
for(int i=;i<M;i++){
if(!f[i]) prime[cnt++]=i;
for(int j=;j<cnt&&i*prime[j]<M;j++){
f[i*prime[j]]=;
if(i%prime[j]==) break;
}
}
}
void solve(int m)
{
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++) p[i]=;
for(int i=;i<cnt&&prime[i]<=n;i++){
double t=log(prime[i]);
for(int j=n;j>=prime[i];j--){
for(int k=prime[i],num=;k<=j;k*=prime[i],num++)
if(dp[j-k]+t*num>dp[j]){
dp[j]=dp[j-k]+t*num;
p[j]=p[j-k]*k%m;
}
}
}
}
int main()
{
int m;
init();
while(scanf("%d%d",&n,&m)!=EOF){
solve(m);
printf("%d\n",p[n]);
}
return ;
}
最新文章
- 网站常用UI整理
- Memcached目录
- Box2D淌坑日记: 关节(Joint)和旋转关节(b2RevoluteJoint)
- C语言 ---- 基本数据类型和基本运算 iOS学习-----细碎知识点总结
- rpm包形式安装MySQL
- Mysql进阶(二)
- windows下查看某个端口被哪个程序占用的方法
- c#发送邮件样例
- DBA 经典面试题(3)
- Swift - 给图片添加文字水印(图片上写文字,并可设置位置和样式)
- Python多线程爬虫与多种数据存储方式实现(Python爬虫实战2)
- 解压.bz2失败
- Swiper.js的腾讯新闻演示
- 当前数据库普遍使用wait-for graph等待图来进行死锁检测
- centos 专题-各种配置应有尽有
- hdu 1286 找新朋友 欧拉函数模版题
- Linux文件系统测试工具
- java.lang.NoSuchMethodError: javax.servlet.ServletContext.getContextPath()Ljava/lang/String;
- 简单地理解HTTPS 转
- Luogu-3250 [HNOI2016]网络
热门文章
- hdu 2066 一个人的旅行
- JavaScript高级程序设计之动态脚本及动态样式
- Go中简单的文件读写
- [译]rabbitmq 2.2 Building from the bottom: queues
- MongoDB 数据类型
- 008--VS2013 C++ 位图半透明化(另一种显示)
- ASP.NET中Global.asax 文件是什么?
- 【收藏】Linux下tomcat内存配置
- 简单的C语言小学四则运算设计
- 1.项目开发-->;Memcached之ASP.NET实现