【BZOJ】1053: [HAOI2007]反素数ant

时间:2021-11-22 07:01:22

1053: [HAOI2007]反素数ant

Description:

g(x)表示x的约数个数,反素数:对于任意的i (i < x),均有g(i) < g(x),则x为反素数;现在输入不超过2e9的数,要你找出不超过N的最大的反素数;

坑点:里面的反素数是严格小于,所以对于相同的约数要取较小的。

思路:直接深搜外加剪枝即可;

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define inf 0x7fffffff
int p[]={,,,,,,,,,,,,,,,};
int n, cnt,ans;
void dfs(int dept,int val,int num,int last)
{
if(dept >= ) return ;
if(num > cnt){
cnt = num;
ans = val;
}
if(num == cnt) ans = min(ans,val);
for(int i = ;i <= last;i++){
if(n/p[dept] < val) break;
dfs(dept+,val *= p[dept],num*(i+),i);
}
}
int main()
{
ans = inf;
scanf("%d",&n);
dfs(,,,);
cout<<ans;
}