[HAOI2007]反素数ant

Time Limit:10000MS  Memory Limit:165536K
Total Submit:54 Accepted:33
Case Time Limit:1000MS

Description

反质数（ant）
对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。
如果某个正整数x满足：g(x)>g(i) 0

Input

一个数N（1<=N<=2,000,000,000）。

Output

不超过N的最大的反质数。

Sample Input

1000

Sample Output

840

Source
只能搜呗。。首先素因子最多是前10个，同时各个因子的幂肯定递减。。然后就随便搜了。。实际上还可以加一些剪枝的，比如估价函数之类的，设当前搜到素数p，上限为N，那么显然最多还能将素因子*2^Log（p,N）倍。。
Code：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxp=1000;
int Ps[maxp],pnt=0,N;
typedef long long ll;
bool IsPrime(int p)
{
if(p==2)return true;
if(p%2==0) return false;
for(int i=3;i*i<=p;i+=2)if(p%i==0) return false;
return true;
}
struct Answer
{
int ans,num;
Answer(){ans=1;num=1;}
void Update(const Answer&a)
{
if(a.ans>ans||(a.ans==ans&&a.num<num)) *this=a;
}
Answer Mul(int x,int c)
{
Answer ret;
ret.ans=ans*(c+1);
ret.num=num*x;
return ret;
}
}Ans;
void GetPrime()
{
for(int i=2;i<maxp&&pnt<9;i++) if(IsPrime(i)) Ps[pnt++]=i;
}
void dfs(int now,int pre,ll N,Answer a)
{
if(N<Ps[now]||now>=pnt||!pre){Ans.Update(a);return;}
ll s=1;rep(i,pre) s*=Ps[now];
for(int i=pre;i>=0;–i)
{
if(s<=N)dfs(now+1,i,N/s,a.Mul(s,i));
s/=Ps[now];
}
}
int main()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
cin>>N;
GetPrime();
dfs(0,15,N,Answer());
long long k=1;
cout<<Ans.num<<endl;
}