B - Fadi and LCM CodeForces - 1285C 质因子
2024-09-05 04:06:01
题目大意很简单,给你一个整数X,让你求a和b,使得max(a,b)尽可能的小,然后打印a,b
题解:想到了质因子分解,也考虑到了暴力,但是觉得暴力的话会TLE,所以打算用贪心做,然后就一直Wa......。看人家的题解,,就是暴力..将求出的质因子分为两部分即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll M=1E12+;
const ll N=1e6+;
ll arr[N];
ll pos=;
bool mp[N];
ll ans=M;
void dfs(ll a,ll b,ll p){
ans=min(ans,max(a,b));
if(p>=pos) return ;
dfs(a/arr[p],b,p+);
dfs(a,b/arr[p],p+);
}
int main(){
ll x;
cin>>x;
ll x1=x;
ll q=sqrt(x);
for(ll i=;i<=q;i++){
if(x%i==)arr[pos++]=;
while(x%i==){
x/=i;
arr[pos-]*=i;
}
}
if(x!=) arr[pos++]=x;
ll a=x1,b=x1;
dfs(x1,x1,);
cout<<ans<<" "<<x1/ans<<endl;
return ;
}
最新文章
- ASP.NET MVC5+EF6+EasyUI 后台管理系统(61)-如何使用框架来开发
- BZOJ2007——[Noi2010]海拔
- JS写随机数
- MySQL查询优化:查询慢原因和解决技巧
- IIS:开启GZIP压缩效率对比及部署方法
- POJ1038 - Bugs Integrated, Inc.(状态压缩DP)
- 通过JS判断联网类型和连接状态
- Nginx 搭建反向代理服务器过程详解
- 如何在VUE项目中添加ESLint
- 帝国cms打开慢
- Spring理解IOC,DI,AOP作用,概念,理解。
- [转]一个研究生毕业以后的人生规划[ZZ]
- selenium 简单粗暴的定位方法
- 1--Python 入门--Python基础数据类型
- Linux系统服务之inetd
- java 获取当前日期和特殊日期格式转换
- ASP.NET MVC Bundles 之学习笔记
- HDFS读写流程
- 如何获取Android唯一标识(唯一序列号)
- JDK中枚举的底层实现
热门文章
- RoBERTa
- [二分,multiset] 2019 Multi-University Training Contest 10 Welcome Party
- 【SQL SERVER重新认识】数据内部存储结构简单探索
- TorchScript简介
- 深入理解JavaScript中的堆与栈 、浅拷贝与深拷贝
- Ceph学习笔记(2)- CRUSH数据分布算法
- 一篇漫画故事带你理解透HTTPS(下)
- yum,rpm等失效,使用系统安装包ISO文件降级程序恢复系统
- 新手必学linux文本文件编辑命令 vi vim.....
- MTK Android ListPreference的用法