「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;
}