bzoj1053 [HAOI2007] 反素数ant

本文主要是介绍bzoj1053 [HAOI2007] 反素数ant，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门
Description

　　对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足：g(x)>g(i)0 < i < x，则称x为反质数。例如，整数1，2，4，6等都是反质数。现在给定一个数N，你能求出不超过N的最大的反质数么？
Input
　　一个数N（1<=N<=2,000,000,000）。
Output
　　不超过N的最大的反质数。
Sample Input
1000
Sample Output
840

题解

乍一看这道题很像一道数轮题，于是苦心钻研欧拉函数无果= =
然而这道题跟欧拉函数半毛钱关系都没有，事实上是一道搜索
可以枚举所有的小质数，由于唯一分解定理，若一个数x可以被分解成
　　　　　　　　　　　　　　　
则

所以枚举完所有小质数的直属以后就可以直接求其因子数量了
又由于题目要求的是g(x)>g(i) 0 < i < x，所以当因子数量相同时，更小的数才是答案
所以枚举指数的时候较大的质数的指数一定小于等于之前的质数的指数。
搜索即可

#include<cstdio>
int P[13]={0,2,3,5,7,11,13,17,19,23,29,31,37};
int n,maxn;
long long ans;
void dfs(long long num,int tot,int d,int last)
{if(tot>maxn||tot==maxn&&num<ans) maxn=tot,ans=num;if(d==13) return;long long tmp=1;for(int i=1;i<=last;i++){tmp*=P[d];if(tmp*num>n) break;dfs(num*tmp,tot*(i+1),d+1,i);}
}
int main()
{scanf("%d",&n);dfs(1,1,1,27);printf("%lld",ans);return 0;
}

这篇关于bzoj1053 [HAOI2007] 反素数ant的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---