提供一个随便口胡的证明过程。

题目大意

设 $d(n)$ 表示 $n$ 的约数个数，求最大的 $x$ 满足 $\forall i \in (0, x), d(i)<d(x)$。

问题的转化

问题可以转化为：

1. 求 $[1, n]$ 因数个数最多的数。

2. 若相同的值有多个，则取最小值。

证明

假设 $x$ 为唯一的因数个数最多的数，显然 $x$ 一定是一个反素数。再假设有一个更大的反素数 $y$ 满足 $y > x,d(y) < d(x)$，则与反素数的定义相矛盾，故因数个数最多的数为区间内最大的反素数。

如果存在多个相同的最大值，那么显然除了第一个，都不是反素数。

解法

根据唯一分解定理，我们有：对于任意一个正整数 $x$，它可以写成 $\prod p_i^{a_i}$，其中 $p_i$ 为质数，$a_i \in [0, \infin]$。

根据乘法原理，有 $d(x)=\prod(a_i + 1)$。

所以我们可以考虑搜索 $a_i$，求出 $d(x)$。

但是我们知道素数有无穷多个，所以我们需要进一步的推导。

结论：$a_i$ 是单调不升的。

证明

设 $x = \prod p_i^{a_i}$ 是反素数，其中 $a_i$ 是无序的。

设 $a_i$ 降序排序后变成了 $b_i$，$y = \prod p_i^{b_i}$，显然 $y < x$ 而 $d(y)=d(x)$。

根据上方问题转化-2，我们可以知道，$x$ 不是反素数，与假设相悖。

也就是说，$a_i$ 是有序的。

所以我们只需要前面的少数素数就可以了。

参考 oeis A002110 我们发现第 10 个素数的前缀积已经超过了数据范围，因此我们可以只用 10 个素数。

代码

根据以上的推理我们可以写出代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int prime[] = {0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,51};
int f[20], n, AnsNum, AnsDiv;

//dfs: {Current Depth, Current Number, Current Divisors}

inline void dfs(int dep, int num, int div) {
    if(div > AnsDiv || (div == AnsDiv && num < AnsNum)) AnsNum = num, AnsDiv = div;
    if(dep > 10) return;
    int nxp = 1;
    for(register int i = 1; i <= f[dep - 1]; i++) {
        nxp *= prime[dep];
        f[dep] = i;
        int NewNum = num * nxp, NewDiv = div * (i + 1);
        if(NewNum > n) break;
        dfs(dep + 1, NewNum, NewDiv);
    }
}

signed main() {
    scanf("%lld", &n);
    f[0] = 30;
    dfs(1, 1, 1);
    printf("%lld", AnsNum);
    return 0;
}

https://blog.csdn.net/tenkuo/article/details/153814611

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll prime[11]={0,2,3,5,7,11,13,17,19,23,29},pnum[15],ans1,ans2,n;
//prime[i]表示第i个素数，pnum[i]表示第i个素数的个数
//ans1表示搜索到的 "约数之霸"
//ans2表示 "约数之霸" 的 约数个数 
void dfs(ll now,ll gnum,ll nn)//gnum表示nn这个数的约数个数，now表示当前准备用第now个素数作为原材料 
{
    if(now==11)
    {
        if( gnum>ans2 || (ans2==gnum && ans1>nn) )
        {
            ans1=nn;ans2=gnum;
        }
        return ;
    }
    for(ll i=0;i<=pnum[now-1];i++)
    {
        pnum[now]=i;
        dfs(now+1,gnum*(i+1),nn);
        nn=nn*prime[now];if(nn>n) return ;
    }
}
int main()
{
    cin>>n;
    pnum[0]=32;
	ans1=0x7fffffff;
	ans2=1;
    dfs(1,1,1);
    cout<<ans1<<endl;
    return 0;
}