1053: [HAOI2007]反素数ant
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的最大的反质数么？
nput

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

Output

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

Sample Input

1000
Sample Output

840

#include <cstdio>
#include <iostream>
#include <cstring>
#define ll long long 
using namespace std;
long long prime[14]={
  0,2,3,5,7,11,13,17,19,23,29,31,37};
int n;
int ans=0;
long long hx=0; 
void dfs(int now,ll num,int tot,int last){
  //当前第几个质数，当前数 ,因子数,上一个数的次数
//因为容易得到，小的因子多一定好过大的因子多 
    if(now==12)
    {
        if(tot>ans||(tot==ans&&num<hx)){
        ans=tot;
        hx=num;
        }   
        return ;
        return;
    }
    int t=1;
    for(int i=0;i<=last;i++){
        dfs(now+1,num*t,tot*(i+1),i);
        t=t*prime[now];
        if(t*num>n) break;
    }
}
int main(){
    scanf("%d",&n);
    dfs(1,1,1,20);
    printf("%lld",hx);
    return 0;
}

题目要求不超过n的因子数最多的最大数，若有多解，则输出最小数，很明显小的因子多一定好过大的因子多 ，而质数的个数也不会超过12，那么就开始搜索
然后这里有一个定理：
一个数的因子数=它各个质因子的个数+1的乘积
eg:12=2^2*3
所以12 的因子数为（2+1）*(1+1)=6
我也不会证明呵呵呵