「HAOI2007」反素数 - 搜索

对于任何正整数 ,其约数的个数记作 ,例如 。如果某个正整数 对于任何 都满足 ,则称 为反质数。

给定一个数 ,求最大的不超过 的反质数。

链接

BZOJ 1053

题解

一个反质数 一定是 内约数个数最多的数,并且不存在一个 使 的约数个数与 的相等。

所以,对于因子数量相同的数,较小的才有可能是反质数。由此可知,反质数的质因子一定是从 开始连续的若干个质数。

的唯一分解式为 。则 的约数个数 。假设存在一个 满足 不是连续的质数,则令 的下一个质数, 向后顺延,这样得到的唯一分解式中, 不变,而 变小了。上述推论得证。

所以,本题的答案的质因子一定是前若干个质数,通过计算可知,前 个质数()的积大于

搜索每个质数的次数,如果得到一个比当前答案约数数量更多的数,或者得到一个与当前答案约数数量相等但本身更小的数,则更新答案。

代码

#include <cstdio>

const int MAXN = 2e9;

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

int n, cntAns;
long long ans;

inline void search(int i, long long x, int cnt) {
    if (i == PRIMES_CNT) {
        if ((cnt == cntAns && x < ans) || (cnt > cntAns)) {
            ans = x;
            cntAns = cnt;
            // printf("%lld\n", ans);
        }
        return;
    }

    long long t = 1;
    for (int j = 0; x * t <= n; j++) {
        search(i + 1, x * t, cnt * (j + 1));
        t *= PRIMES[i];
    }
}

int main() {
    scanf("%d", &n);
    search(0, 1, 1);
    printf("%lld\n", ans);

    return 0;
}