Description：

对于任何正整数 $x$ ，其约数的个数记作 $g(x)$ 。如果某个正整数 $x$ 满足： $g(x)>g(i) \text{ }0<i<x$ ，则称 $x$ 为反质数，求出不超过 $N$ 的最大的反质数。

$1\le n \le 2\times 10^9$

Solution：

由唯一分解定理得 $x=\prod p_i^{q_i}$ ，则对于一个反质数，一定有 $q_i>q_j(i<j)$ ，因为由约数个数定理得 $\sigma_0(x)=\prod(q_i+1)$ ，如果 $q_i<q_j(i<j)$ ，则可以交换 $q_i$ 和 $q_j$ ，得到一个更小的约数个数相同的数，一定不合法，于是就可以搜索了。

由于前 $10$ 个质数的积大于 $2\times10^9$ ，于是只用这些质数搜即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

ll n;

ll prime[13] = {0,2,3,5,7,11,13,17,19,23,29};

ll ans1 = 0,ans2;

void dfs(ll cur,ll pos,ll tot,ll power)

{

    if(cur > n)return;

    if(pos == 13)

    {

        if(tot > ans1 || (tot == ans1 && cur < ans2))

        {

            ans1 = tot;

            ans2 = cur;

        }

        return;

    }

    for(ll i = 0;i <= power;++i)

    {

        dfs(cur,pos + 1,tot * (ll)(i + 1),i);

        cur *= prime[pos];

        if(cur > n)break;

    }

    return;

}

int main()

{

    cin >> n;

    dfs(1,1,1,31);

    cout << ans2 << endl;

    return 0;

}