[ZOJ2069]Greatest Least Common Multiple
2024-10-09 16:14:11
[ZOJ2069]Greatest Least Common Multiple
题目大意:
给定一个正整数\(n\),将其分成若干个正整数之和,最大化这些数的LCM。保证答案小于\(10^{25}\)。
思路:
由于答案\(\le10^{25}\),则\(n\le540\)。
可以证明一定存在一种方案使得拆分后各数互质且答案最大。
\(f[i][j]\)表示考虑前\(i\)种质数,组成的和为\(j\)的答案。转移时枚举从\(n\)中拆出这个质数的多少次方。
由于OJ上不支持__int128
,所以直接最后打表即可。
打表程序:
#include<cstdio>
#include<cctype>
#include<numeric>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
const int N=541,P=N;
typedef long long int64;
typedef __int128 int128;
int128 f[P][N];
int128 gcd(const int128 &a,const int128 &b) {
return b?gcd(b,a%b):a;
}
inline int128 lcm(const int128 &a,const int128 &b) {
return a/gcd(a,b)*b;
}
void print(const int128 &x) {
if(x>9) print(x/10);
putchar(x%10+'0');
}
bool vis[N];
int p[P];
inline void sieve() {
for(register int i=2;i<N;i++) {
if(!vis[i]) p[++p[0]]=i;
for(register int j=1;j<=p[0]&&p[j]*i<N;j++) {
vis[p[j]*i]=true;
if(i%p[j]==0) break;
}
}
}
int main() {
sieve();
std::fill(&f[0][0],&f[0][N],1);
for(register int i=1;i<=p[0];i++) {
f[i][0]=f[i-1][0];
for(register int j=1;j<N;j++) {
f[i][j]=std::max(f[i-1][j],f[i][j-1]);
for(register int q=p[i];q<=j;q*=p[i]) {
f[i][j]=std::max(f[i][j],f[i-1][j-q]*q);
}
}
}
putchar('{');
for(register int i=0;i<N;i++) {
if(i!=0) putchar(',');
putchar('"');print(f[p[0]][i]);putchar('"');
}
puts("};");
return 0;
}
最新文章
- linux下常见解压缩命令
- LeetCode&mdash;&mdash;Best Time to Buy and Sell Stock III (股票买卖时机问题3)
- sys.stdout.write与sys.sterr.write(三)
- Socket网络编程-基础篇
- 027医疗项目-模块二:药品目录的导入导出-导入功能的Action的编写
- Python: Lambda Functions
- ### About Multi-Object Tracking
- C语言基础学习基本数据类型-Char类型
- html 知识
- Android中TextView中内容不换行的解决方法
- Linux网卡配置与绑定
- Selenium2+python自动化28-table定位
- 201521123040《Java程序设计》第1周学习总结
- C#、.NET Framework、CLR的关系
- (十六)java中的String
- 判断浏览器的类型$_SERVER[&#39;HTTP_USER_AGENT&#39;]和语言$_SERVER[&#39;HTTP_ACCEPT_LANGUAGE&#39;]
- group by having 和where区别联系
- React(0.13) hello world
- 风景区的面积及道路状况分析问题 test
- 带你了解数据库中JOIN的用法
热门文章
- linux-umount挂载点无法卸载:device is busy(解决)
- mac下Fiddler的安装-启动
- C++设计模式——单例模式(转)
- 论文阅读笔记二十三:Learning to Segment Instances in Videos with Spatial Propagation Network(CVPR2017)
- matlab转c++代码实现(主要包含C++ std::vector,std::pair学习,包含数组与常数相乘,数组相加减,将数组拉成一维向量,图片的读入等内容)
- 【CF809D】Hitchhiking in the Baltic States
- [转]Maven与nexus关系
- Windows下80端口被进程System占用的解决方法
- vue中的provide/inject的学习使用
- 51nod1967 路径定向 Fleury