【SCOI2003】巴蜀1088 Antiprime数

Description
如果一个自然数n（n>=1），满足所有小于n的自然数（>=1）的约数个数都小于n的约数个数，则n是一个Antiprime数。譬如：1,
2, 4, 6, 12, 24。 任务：编一个程序：
1、从ANT.IN中读入自然数n。
2、计算不大于n的最大Antiprime数。
3、将结果输出到ANT.OUT中。 Input 输入只有一个整数，n（1 <= n <= 2 000 000 000）。 Output 输出只包含一个整数，即不大于n的最大Antiprime数。

首先问题可以转化成求n以内约数最多的数，约数相同则取小的。
一个数x=a1^p1* a2^p2* …* an^pn(a是质数)的约数个数为(p1+1)* (p2+1)* …* (pn+1)。
考虑到2* 3* 5* 7* 11* 13* 17* 19* 23* 27>2e9，可以将27之前的素数打表，之后搜索每个素数的次数即可。
显然可以得到这个剪枝：从2向后，每个素数的指数单调不增。从而也有一个推论，就是不能跳着取素数。这样运行速度就很快了。

#include<cstdio>
#include<cstring>
int p[]={0,2,3,5,7,11,13,17,19,23,0},m,best;
long long n,ans;
void dfs(long long x,int k,int mx,long long now)
{
    if (now>best||(now==best&&x<ans))
    {
        ans=x;
        best=now;
    }
    if (!p[k]) return;
    int cnt=1;
    for (x*=p[k];x<=n&&cnt<=mx;x*=p[k],cnt++)
      dfs(x,k+1,cnt,now*(cnt+1));
}
int main()
{
    scanf("%lld",&n);
    dfs(1,1,1e8,1);
    printf("%d\n",ans);
}