https://www.lydsy.com/JudgeOnline/problem.php?id=1053
https://www.luogu.org/problemnew/show/P1463
定义:
对于任何正整数x,其约数的个数记作g(x)。例如g(1)=1、g(6)=4。
如果某个正整数x满足:g(x)>g(i) 0<i<x,则称x为反质数。
题解:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long n;
int p[20]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,51};
long long maxn=-1,num=-1;//num是因子最大时小于n的最大数,maxn是最大因子数
void get(long long m,int f,int t,int pr)
{ //f为当前质数的编号 ,当前指数<pr
//t为当前约数的个数
if(t>maxn||(t==maxn&&m<num))//更新最优解
num=m,maxn=t;
for(int i=1;i<=pr;i++){//j表示的是当前正在搜索的指数
if(n/m<p[f])break;//若不满足条件就跳出循环(i表示的是当前的m)
m*=p[f];
if(m<=n) get(m,f+1,t*(i+1),i); //若i(即当前的m)在区间[1,n]内就继续搜索。
}
}
int main()
{
cin>>n;
get(1,1,1,30);
cout<<num<<endl;
}