对于任意的正整数\(x\)，记其约数的个数为\(g(x)\)。现在定义反素数：对于\(0<i<x\)，都有\(g(x)>g(i)\)，那么就称x为反素数。
现在给定一个数N,满足\(1\leq N\leq 2*10^9\)，求出不超过\(N\)的最大的反素数。
由反素数的定义我们知道，若\(x\)为反素数，那么\(x\)肯定是具有相同约数个数的数中最小的那一个；并且x的约数个数应该是最多的。
很明显直接枚举肯定要炸。观察到\(N\)不会超过\(2*10^9\)，那么就可以知道：\(1\)~\(N\)中任何数质因子都不超过10个，并且所有质因子的指数总和不超过30。
然后。。反素数还有一个关键的性质，就是将它质因数分解过后，其指数是单调不增的。证明的话可以考虑交换两项的指数来考虑，对于一个\(p^{k_1}\)，假设存在一个\(q^{k_2}\)并且满足\(p<q,k_1<k_2\)，那么交换\(k1,k2\)，会得到一个更小的且约数相同的数。
那么之后我们可以直接利用这些性质爆搜就好了。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 105;
ll n;
ll prime[N] = {1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
ll c[N];
ll qp(ll a, ll b) {
ll ans = 1 ;
while (b) {
if(b & 1)
ans = ans * a;
a = a * a;
b >>= 1;
}
return ans ;
}
ll ans, num;
void dfs(int k, int p, ll mul) {
if(k == 11) {
ll tmp = 1;
for(int i = 1; i <= 10; i++) {
tmp *= (c[i] + 1);
}
if(tmp > num) {
num = tmp;
ans = mul;
} else if(tmp == num && ans > mul) {
ans = mul;
}
return ;
}
ll cnt = 0;
for(; cnt <= p; cnt++) {
if(qp(prime[k], cnt)*mul > n) {
if(cnt > 0)
cnt--;
break ;
}
}
cnt = min(cnt , (ll)p);
for(int i = cnt; i >= 0; i--) {
c[k] = i;
dfs(k + 1, cnt, mul * qp(prime[k], i));
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
dfs(1, 31, 1);
cout << ans;
return 0;
}