数论ZOJ 2562

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

题意：给定一个数N，求小于等于N的所有数当中，约数最多的一个数，如果存在多个这样的数，输出其中最大的一个。

分析：反素数定义：对于任何正整数x,其约数的个数记做g(x).例如g(1)=1,g(6)=4.如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数。

性质一:一个反素数的质因子必然是从2开始连续的质数。
性质二:p=2^t1*3^t2*5^t3*7^t4.....必然t1>=t2>=t3>=....

LL  p[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47} ;
LL  num , fnum , x ;void dfs(LL n , LL fn , int id , LL limit){if(id == 15) return  ;if(fn > fnum){num = n ;fnum = fn ;}else if(fn == fnum)  num = min(num , n) ;LL t = n ;for(LL i = 1 ; i <= limit ; i++){t *= p[id] ;if(t > x) break ;dfs(t , fn*(i+1) , id+1 , i) ;}
}int  main(){while(cin>>x){num = 1 ;fnum = 1 ;dfs(1 , 1 , 0 , 50) ;cout<<num<<endl ;}return 0 ;
}

这篇关于数论ZOJ 2562的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---