首页 > 代码库 > 巴蜀1088 Antiprime数
巴蜀1088 Antiprime数
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），搜索答案。
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #define LL long long 8 using namespace std; 9 const int pri[11]={0,2,3,5,7,11,13,17,19,23,0};10 LL ans=0;11 LL mx=0;12 LL n;13 void dfs(LL now,LL res,int last_mx,int pos){14 //当前累计值，当前累计因数个数，上个质因数使用次数，枚举位置 15 if(res>mx || (res==mx && now<ans)){16 mx=res; ans=now;17 }18 if(pos==10)return;19 for(int cnt=1;cnt<=last_mx;cnt++){20 now*=pri[pos];21 if(now>n)return;22 dfs(now,res*(cnt+1),cnt,pos+1);23 }24 return;25 }26 int main(){27 scanf("%lld",&n);28 dfs(1,1,500,1);29 printf("%lld\n",ans);30 return 0;31 }
巴蜀1088 Antiprime数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。