hihoCoder 1187
2024-08-31 05:12:30
今天BC爆0了。。。。但是日子还是要过的。。。。要回学校毕业了~~大学就这么“荒废”了。
这个是hihoCoder的1187,比较基础的一道题。
题目链接:
http://hihocoder.com/problemset/problem/1187
首先我们想,任何一个数可以质因数分解,且分解的方法唯一。
n = (p1 ^ k1) * (p2 ^ k2) * .... * (ps ^ ks)
约数(n) = (k1+1)*(k2+1)*(k3+1)* .... *(ks+1)
那么剩下的问题就简单了,贪心,显然在约数个数相同的情况下,pi越小越好。
暴力枚举ki,pi显然不用搜太多,目测搜到43就绰绰有余了。
ki搜到60即可,不放行的话,还可以参考线这个优化,k1 >= k2 >= ... >= ki。
证明不复杂~~
代码:
#include <bits/stdc++.h> using namespace std;
typedef long long int64;
int64 prim[] = {, , , , , , , , , , , , , }; int64 ans, Max;
int64 n; void dfs( int id, int pre_cnt, int64 num, int64 res ){
if( res > Max ){
ans = num;
Max = res;
}else if( res == Max ){
ans = min( ans, num );
} int64 tmp = ;
for( int i = ; i <= ; ++i ){
tmp *= prim[id];
if( num * tmp > n )
return;
dfs( id+, i, num*tmp, res*(i+) );
}
} int main(void){
while(cin >> n){
ans = , Max = ; int64 tmp = ;
for( int i = ; i <= ; ++i ){
tmp *= prim[];
if( tmp <= n )
dfs( , i, tmp, i+ );
} printf("%lld\n", ans);
} return ;
}
最新文章
- 代码的坏味道(22)——不完美的库类(Incomplete Library Class)
- C#中级-常用多线程操作(持续更新)
- mediawiki安装
- HttpClient(JAVA)使用笔记
- SPOJ287 Smart Network Administrator(最大流)
- java Reentrant Lock
- Qt之窗体拖拽、自适应分辨率、自适应大小 good
- Lambert
- .NET踩坑记录【不断更新】
- (原)centos7安装和使用greenplum4.3.12(详细版)
- JavaScript 实现二叉树
- HttpClientFactory与Steeltoe结合来完成服务发现
- cf919D 线性dp+拓扑排序
- vue双向绑定的时候把遍历的数组转为了字符串,并且再转回去数组进行绑定
- SSM三大框架整合
- [20171211]ora-16014 11g.txt
- NOIP2018TG题解
- JMeter安装+配置+运行
- js基础知识入门总结
- iermu爱耳目
热门文章
- THREE.js代码备份——canvas - geometry - earth(球体贴纹理)
- 【sqli-labs】 less59 GET -Challenge -Double Query -5 queries allowed -Variation2 (GET型 挑战 双查询 只允许5次查询 变化2)
- win10系统安装postgresql后无法连接
- centos 7 配置nginx
- NOIWC2019 冬眠记
- Django REST framework - 视图
- Excel 2010/2013/2016在鼠标右键新建xls或xlsx文件后,打开报错“无法打开文件”“文件格式或文件扩展名无效”
- Python获取当前系统时间
- 多校第六场 1003 hdu 5355 Cake(贪心)
- c++ 11 thread 初试