题目地址：洛谷：【P1463】[HAOI2007]反素数 – 洛谷、BZOJ：Problem 1053. — [HAOI2007]反素数ant

题目描述

对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。
如果某个正整数x满足：g(x)>g(i) 0<i<x，则称x为反质数。例如，整数1，2，4，6等都是反质数。
现在给定一个数N，你能求出不超过N的最大的反质数么？

输入输出格式

输入格式：
一个数N（1<=N<=2,000,000,000）。

输出格式：
不超过N的最大的反质数。

输入输出样例

输入样例#1：

1000

输出样例#1：

840

题解

我们注意到如果将一个数分解成质数幂的乘积即 \displaystyle x = \prod p_i^{k_i} ，它因数的个数实际上就是 \displaystyle \prod (k_i + 1) 。
考虑到质因数较小的数比较有利，答案一定存在于质因数最小的数中，而前11个质数的乘积实际上已经超过了n的范围，我们可以把前11个质数打个小表，DFS来选择每个质数的数量，寻找答案。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int prime[] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};

int n, ans, acnt;

inline void dfs(LL x, int cnt, int lim, int step) {
    if(step == 12) {
        if((x > ans && cnt > acnt) || (x <= ans && cnt >= acnt)) {
            ans = x; acnt = cnt;
        }
        return;
    }
    LL t = 1;
    for(int i = 0; i <= lim; i++) {
        if(x * t > n) break;
        dfs(x * t, cnt * (i + 1), lim, step + 1);
        t *= prime[step];
    }
}

int main() {
    n = readint();
    dfs(1, 1, 20, 1);
    printf("%d", ans);
    return 0;
}