题意：设g(i) = i的约数个数，若对于某个正整数x，所有0<i<x都有g(i)<g(x)，那么称x为反素数。求不大于n的最大反素数。（n<=2*10^9）
暑假的时候TYQ同学提到一个有趣的概念叫做反素数，看到bzoj第一页有这道题，于是来写一写。
关于约数个数，我们知道什么？约数个数定理：设 x=∏paii ，由乘法原理，约数个数 σ(x)=∏(ai+1) 。筛法可以线性地处理前缀的约数个数。然而，根据数据范围，这是不可行的。
设f(i)=约数个数为i的最小正整数，问题等价于求最小的f(i) <= n。能不能把它和约数个数定理结合起来呢？如果数据范围内所有x的约数个数都很小，暴力枚举一下是可行的。然而怎么估算约数个数呢？
又考虑了一下前缀的lcm，然而lcm(1, 2, 3)=6，lcm(1, 2, 4) = 4，f(3)=4。
反素数有没有什么神奇的性质呢？
看题解……第一条是百度百科，点进去看了一下，给了两条性质：1) 一个反素数的质因子必然是从2开始连续的质数 2) p=2^t1*3^t2*5^t3*7^t4…..必然t1>=t2>=t3>=….
性质一很显然的样子，性质二用逐步调整法容易证明。不看啦，再想一想。
性质一可以推出本题只用考虑前10个素数作为质因子。我想dp一下……于是，又回到那个老问题：如何估算约数个数？我似乎犯蠢啦， O(n√) 啊……性质二在本题中没有发挥作用。
如果即时想到这个界，这道题就能算作自己想出来的啦 QAQ
取个对数，本题回到了我们所熟悉的DAG上最短路的模型。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int prime[11] = {
0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29}, inf = 2e9;
int n, f[11][89450];int main()
{for (int i = 0; i < 11; ++i)for (int j = 0; j < 89450; ++j)f[i][j] = inf;scanf("%d", &n);int m = (sqrt(n)+1)*2;f[0][1] = 1;for (int i = 0; i < 10; ++i)for (int j = 1; j <= m; ++j) {ll x = f[i][j];for (int k = 0; x <= (ll)n; ++k, x *= prime[i+1])f[i+1][j*(k+1)] = min(f[i+1][j*(k+1)], (int)x);}for (int i = 89449; i; --i)if (f[10][i] < inf) {printf("%d\n", f[10][i]);break;}return 0;
}