1053: [HAOI2007]反素数ant
题目连接：
http://www.lydsy.com/JudgeOnline/problem.php?id=1053
Description
对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。
如果某个正整数x满足：g(x)>g(i) 0<i<x，则称x为反质数。例如，整数1，2，4，6等都是反质数。
现在给定一个数N，你能求出不超过N的最大的反质数么？
Input
一个数N（1<=N<=2,000,000,000）。
Output
不超过N的最大的反质数。
Sample Input
1000
Sample Output
840
Hint
题意
题解：
首先你要知道因子个数定理，这个百度都能百度出来
然后我们就好办了，直接dfs就好了
暴力枚举因子就行
这儿有一个剪枝，如果当前素数的出现次数大于比她小的素数的出线次数，这个数显然不是最优的
当然，对于这道题，加不加这个剪枝都是可以过的，所以直接搜就好了
在camp上面有一道这道题的升级版本，也是瞎搜就好了
代码
#include<bits/stdc++.h>
using namespace std;
long long pri[14]={0,2,3,5,7,11,13,17,19,23,29,31,37};
long long ans,res;
long long n;
void dfs(long long now,long long pro,long long num,long long c,long long lastc)
{
//当前取到第几个素数，当前乘积，当前除最后一个数以外的素数个数，最后一个素数个数，上一个素数的个数
//cout<<now<<" "<<pro<<" "<<num<<" "<<c<<" "<<lastc<<endl;
if(num*(c+1)==res&&pro<ans)
ans=pro;
if(num*(c+1)>res)
ans=pro,res=num*(c+1);
if(pro*pri[now]<=n)
dfs(now,pro*pri[now],num,c+1,lastc);
for(int i=now+1;i<13;i++)
if(pro*pri[i]<=n)
dfs(i,pro*pri[i],num*(c+1),1,c);
}
int main()
{
scanf("%lld",&n);
dfs(1,1,1,0,100);
printf("%lld",ans);
}