洛谷1463 [POI2002][HAOI2007]反素数

时隔一年（差两天）来做还是不会做，甚至连我当时写的是什么都没看懂，这充分凸显了写博客的必要性。

题意

求 $\le N$ 的最大数 $x$ ，满足 $\forall 1\le i\le x$ ，$i$ 的约数个数 $<$ $x$ 的约数个数。

题解

直接上搜索。先预处理可能会被用到的质数表，对于每个质数，搜索它可能会被用几次，最后如果约数个数大于当前最大值 或 约数个数相等但数值较小 都对答案进行更新。

剪枝是 因为质数是从小到大排序的，所以可以规定下一个质数的个数一定小于当前的个数。

$x$ 代表当前质数序号，$cnt$ 是约数个数，$sum$ 是当前数值，$last$ 是上次质数用的个数。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

ll n,ans,mxcnt;
ll zs[12]={0,2,3,5,7,11,13,17,19,23,29,31};

void dfs(ll x,ll cnt,ll sum,ll last)
{
    if (x==12)
    {
        if (cnt>mxcnt || (cnt==mxcnt && sum<ans))
        {
            ans=sum;
            mxcnt=cnt;
        }
        return;
    }
    ll s=1;
    for (ll i=0;i<=last;i++)
    {
        dfs(x+1,cnt*(i+1),sum*s,i);
        s*=zs[x];
        if (sum*s>n) break;
    }
}

int main()
{
    scanf("%lld",&n);
    dfs(1,1,1,12);
    return !printf("%lld",ans);
}