分析

• 1~N中最大的反素数是什么呢？是1~N中约数个数最多的最小的那个数，记为x。这是因为小于x的数i对应g(i)值小于g(x)；大于x的所有数j，都不满足g(j) > g(x)，因此反素数就是约数个数最多的最小的那个数。

• 我们想想反素数有什么性质：

（1）int范围内的数据不同的质因子最多有9位。这是因为：

（2）每个质因子的次数最大是30。这是因为$2^{31} > 2 \times 10^9 > 2 ^ {30}$。

（3）反素数对应的质因子的次数一定是递减的（前提：质因子是递增排列的）。这是因为如果不满足这个条件，可以交换这两个质因子的次数，则约数个数不变，但是得到的反素数的值更小，这样更好。

• 我们发现这一题的数据量不大，因此可以使用暴搜。

代码

#include <iostream>

using namespace std;

typedef long long LL;

int primes[9] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
int maxd, number;  // 当前最好结果number对应的约数个数为maxd
int n;

// 当前遍历到primes[u], 且primes[u]出现次数不能超过last
// 当前得到的数据为p, 且此时p对应的约数个数为s各
void dfs(int u, int last, int p, int s) {

    if (s > maxd || s == maxd && p < number) {
        maxd = s;
        number = p;
    }

    if (u == 9) return;

    for (int i = 1; i <= last; i++) {
        if ((LL)p * primes[u] > n) break;
        p *= primes[u];
        dfs(u + 1, i, p, s * (i + 1));
    }
}

int main() {

    cin >> n;

    dfs(0, 30, 1, 1);

    cout << number << endl;

    return 0;
}