以下证明来自算法竞赛进阶指南
引理一： 答案就是 ([1,n]) 之间约数个数最多的最小的数。
证明： 记 (m) 是 ([1,n]) 之间约数个数最多的最小的数。则
- (forall i in [1,m-1],g(i)<g(m));
- (forall i in [m+1,n],g(m) geq g(i))。
(1)说明 (m) 是一个反质数，(2)说明 (m) 以后的数都不是反质数。证毕。
引理二： ([1,n]) 间的任何数不同质因子个数不会超过十个。
证明： (2 imes 3 imes 5 imes 7 imes 11 imes 13 imes 17 imes 19 imes 23 imes 29 imes 31=200560490130)。
所以也有所有指数和不超过 (30)，因为 (2^{30}>2 imes 10^9)。
引理三： 答案必能表示成 (2^{c_1} imes 3^{c_2} imes 5^{c_3} imes 7^{c_4} imes 11^{c_5} imes 13^{c_6} imes 17^{c_7} imes 19^{c_8} imes 23^{c_9} imes 29^{c_{10}})。且对于 (i < j)总有 (c_i geq c_j)。(c_i geq 0)。
证明： 倘若分解下来有个底数不属于这十个质数，记这个底数的幂为 (p^c)，那么这十个质数里头必定有一个及以上的数不为答案的因子。记这个数为 (q)，那么 (q^c imes m/p^c)约数个数和原答案相同且更优。
若对于 (i < j)有 (c_i < c_j)，则可用交换指数的方法证明之。
然后 dfs 指数即可。
#include <iostream>
#include <cstdio>
using namespace std;
int n, ans, hmn;
typedef long long ll;
const int pri[]={0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
void dfs(int x, int l, ll num, int yue){
if(x==11){
if(hmn<yue) hmn = yue, ans = num;
else if(hmn==yue && ans>num) ans = num;
return ;
}
int t=1;
for(int i=0; i<=l; i++){
dfs(x+1, i, num*t, yue*(i+1));
t *= pri[x];
if(num*t>n) break;
}
}
int main(){
cin>>n;
ans = 2000000005;
dfs(1, 30, 1, 1);
cout<<ans<<endl;
return 0;
}