首页 > 代码库 > zoj 2562
zoj 2562
典型的反素数
对于任何正整数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>=....
#include <iostream>
using namespace std;
typedef long long ll;
int pri[20]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
ll n;
ll ans,s;
void dfs (ll num,ll k,ll sum,ll limit){ //num：当前枚举到的数，k：枚举到的第k大的质因子；sum：该数的约数个数；limit：质因子个数上限；
if (sum>s||(sum==s&&num<ans)) //s：结果的约数个数；ans：结果；
s=sum,ans=num;
if (k>14)
return ;
for (int i=1;i<=limit;i++){
num*=pri[k];
if (num>n)
break ;
dfs (num,k+1,sum*(i+1),i);
}
return ;
}
int main (){
while (cin>>n){
s=0;
dfs (1,0,1,50);
cout<<ans<<endl;
}
return 0;
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。