巴蜀1088 Antiprime数
2024-10-20 11:31:37
Description
如果一个自然数n(n>=1),满足所有小于n的自然数(>=1)的约数个数都小于n的约数个数,则n是一个Antiprime数。譬如:1, 2, 4, 6, 12, 24。
任务:编一个程序:
1、从ANT.IN中读入自然数n。
2、计算不大于n的最大Antiprime数。
3、将结果输出到ANT.OUT中。
任务:编一个程序:
1、从ANT.IN中读入自然数n。
2、计算不大于n的最大Antiprime数。
3、将结果输出到ANT.OUT中。
Input
输入只有一个整数,n(1 <= n <= 2 000 000 000)。
Output
输出只包含一个整数,即不大于n的最大Antiprime数。
Sample Input
1000
Sample Output
840
Source
xinyue
问题可以转化成求n以内约数最多的数,约数相同则取小的。
逆用唯一分解定理,从小到大枚举每个质因数的使用个数(由数据范围限定最多枚举到23),搜索答案。
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;
const int pri[]={,,,,,,,,,,};
LL ans=;
LL mx=;
LL n;
void dfs(LL now,LL res,int last_mx,int pos){
//当前累计值,当前累计因数个数,上个质因数使用次数,枚举位置
if(res>mx || (res==mx && now<ans)){
mx=res; ans=now;
}
if(pos==)return;
for(int cnt=;cnt<=last_mx;cnt++){
now*=pri[pos];
if(now>n)return;
dfs(now,res*(cnt+),cnt,pos+);
}
return;
}
int main(){
scanf("%lld",&n);
dfs(,,,);
printf("%lld\n",ans);
return ;
}
最新文章
- 设置Hyper-V和VMware多个服务之间共存
- JFinal - Log 日志
- jQuery检测滚动条(scroll)是否到达底部
- Cheatsheet: 2015 03.01 ~ 03.31
- ACM数据结构相关资料整理【未完成,待补充】
- Ubuntu下设置Tomcat成为服务(开机启动)
- hibernate api
- ZOJ2099
- mysqlbinlog详解
- February 29(模拟)
- 解锁redis锁的正确姿势
- centos手动配置IP和DNS
- SQLServer删除重复行
- Oracle学习笔记三
- 打印word文档时遇到标记区如何取消
- DTS(待了解)
- javascript中数组总结
- ajax请求完成执行的操作
- web--webstorm的一些常用快捷键
- R(5): sql 数据处理