题目链接
题目描述
对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。
如果某个正整数x满足：g(x)>g(i) 0<i<x，则称x为反质数。例如，整数1，2，4，6等都是反质数。
现在给定一个数N，你能求出不超过N的最大的反质数么？
题目分析
根据反质数的概念和算术基本定理，我们可以知道，若x为反质数，则x=∏piai(pi为质数，pi>pi-1，ai<=ai-1)（对于最后一项限制的说明：若存在ai>ai-1，则交换ai与ai-1所得的数与原来的数因数个数相等，但比原来的数小，故原数非反质数）。
这样，我们只需要从小到大枚举质数，对于每一个质数枚举它的指数进行搜索，判断生成的数是否是满足条件的最大反质数即可，注意如果当前生成的数因数个数与记录的最大因数个数相等，但数本身比记录值小，需要更新记录值，因为原来的数已经不是反质数了。
对于枚举质数的范围，因为2×3×5×7×11×13×17×19×23×29大于N的最大值，故只需枚举这几个质数即可。同时，由于231也已经大于N的最大值，所以指数的上界为31。
代码
1 #include<cstdio> 2 using namespace std; 3 const int prime[11]={0,2,3,5,7,11,13,17,19,23,29}; 4 unsigned long long n,max_factor,ans; 5 void dfs(unsigned long long step,unsigned long long sum,unsigned long long factor,unsigned long long maxn) 6 { 7 if(step>10||sum>n) 8 return; 9 if(max_factor<factor) 10 { 11 max_factor=factor; 12 ans=sum; 13 } 14 else if(max_factor==factor&&ans>sum) 15 ans=sum; 16 unsigned long long t=1; 17 for(unsigned long long i=1;i<=maxn;++i) 18 { 19 t*=prime[step]; 20 dfs(step+1,sum*t,factor*(i+1),i); 21 } 22 return; 23 } 24 int main() 25 { 26 scanf("%llu",&n); 27 dfs(1,1,1,31); 28 printf("%llu",ans); 29 return 0; 30 }