Link
Solve
不知道为什么这道题会变成省选的基础打表
通过分析题意，能得出三个引理
引理1
(1)$N$中的最大的反质数，就是$1$(N)中约数个数最多的数中最小的一个 。
引理2
1~N中任何的不同质因子都不会超过10个，且所有质因子的指数总和不超过30。
引理3
x的质因子是连续的若干个最小的质数，并且质数单调递增。
三个引理的证明就不给了，可以感性理解一下
综上所述，我们可以使用DFS尝试搜索前10个质数的指数，并满足指数递减、总乘积不超过N，同时记录约数的个数。
在这两个限制条件下，搜索量实际非常小，每当搜索出一个满足条件的整数的时候，我们就按照性质一的结论更新答案，最终得到约数个数最多的数中最小的一个。
Code
#include <algorithm>
#include <iostream>
#include <cstdio>
#define ll long long
using namespace std ;
int pri[15] = {0,2,3,5,7,11,13,17,19,23,29,31};
//最小的11个质数
ll best = -1 , num = -1 ;
//万一答案是0呢？
int n ;
void dfs(ll x , int rest , int m, int up)
//x为当前数字的大小，m为当前数字约数的个数
//rest为当前质数的编号，up为小于三十的当前指数和
{
if(m > best || (m == best && x < num))
num = x , best = m ;
//根据性质一的更新答案过程
ll ans = x ;
int i = 0 ;
while(i < up)
{
++ i ;
if(n / ans < pri[rest])
//保证总乘积不超过N
return ;
int kkk = m * (i + 1 ) ;
ans *= pri[rest] ;
if(ans <= n)
dfs(ans , rest + 1 , kkk , i) ;
//保证了质数的单调递减
}
//加上这两个搜索的剪枝，就会感到dfs快的飞起 哈哈哈
}
int main()
//及其卑微的主函数
{
scanf("%d" , &n) ;
dfs(1 , 1 , 1 , 30);
printf("%lld
" , num);
}