算法竞赛进阶指南， 140页，素数，搜索
本题要点：
1 、1 ~ N之间的反素数，就是 1 ~ N 中约数最多的数中最小的一个。
2、 n <= 2 * 10^9, 考虑到 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 *23 * 29 * 31 > 2 * 10^9,
n不可能有多于 10 个的素因子。
3、 同样的素因子组成结构，素因子越小越好。 比如 4312 = 2^3 * 7^2 * 11 , 这个数由， 3， 2， 1 个不同的素因子组成。
4312 的 约数个数 = (3 + 1) * (2 + 1) * (1 + 1) = 24 个。
而 1400 = 2^3 * 5^2 * 7 和 4312 的约数个数一样，但是 1400 优于 4312
4、 因此，将n因式分解后，n = 2^c[1] * 3^c[2] * 5^c[3] * 7^c[4] * 11^c[5] * 13^c[6] * 17^c[7] * 19^c[8] * 23^c[9] * 29^c[10],
指数单调递减， c[1] > = c[2] >= c[3] > = c[4] >= c[5] > = c[6] >= c[7] > = c[8] >= c[9] > = c[10]
5、 写个dfs 搜索即可。
开个数组 cnt[i] 存放第i个素数的个数。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int SIZE = 11;
int prime[SIZE], cnt[SIZE];
int n, ans_cnt = 0;
long long ans = 2e9 + 1;int cacl_cnt() //计算质因数的个数
{
int fac_cnt = 1;for(int i = 1; i <= 10; ++i){
fac_cnt *= (cnt[i] + 1);}return fac_cnt;
}void dfs(long long multi, int cur) //multi 前 cur - 1 个已经选择素数的乘积, cur 表示数组 prime 的下标
{
if(cnt[cur - 1] == 0 || cur > 10){
int count = cacl_cnt();if(ans_cnt < count || (ans_cnt == count && ans > multi)){
ans_cnt = count;ans = multi;}return;}int s = 1, k = 0;while(k <= cnt[cur - 1] && multi * s <= n) {
cnt[cur] = k;dfs(multi * s, cur + 1); ++k;s *= prime[cur];}
}int main()
{
prime[1] = 2, prime[2] = 3, prime[3] = 5, prime[4] = 7, prime[5] = 11, prime[6] = 13;prime[7] = 17, prime[8] = 19, prime[9] = 23, prime[10] = 29;cnt[0] = 30;scanf("%d", &n);dfs(1, 1);printf("%lld\n", ans);return 0;
}/* 1000 *//* 840 */