

BZOJ1053 反素数

题面

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

题解

之前听过这是个打表，结果一直想直接打表出所有反素数，后来发现不幸，还是要用数学方法解决。

对于一个数 $x=\sum\limits_{i=1}^{k} p_i^{a_i}$ ,如果满足对于两个位 $i, j$ ，有 $i < j$ 并且 $a_i < a_j$ 那么显然将 $a_i, a_j$ 对换能够使答案更优，那么可以得到一个结论对于每个可能成为反素数的数的不为 $0$ 的 $\{a\}$ 肯定满足是降序的。

那么我们就可以按照这个来暴搜，由于前 $20$ 个素数的乘积已经大于 $2e9$ 了，所以只需存下并使用前 $20$ 个素数就行了。

然后稍微加一点剪枝。

程序

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
typedef long long ll;

ll N, res, ans;
int pri[] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 51};

int dfs (ll m, int idx, int tot, int num) {
    if (ans < tot || (ans == tot && res > m))
        ans = tot, res = m;
    int j = 0, ntot;
    ll x = m;
    while (j < num) {
        j++;
        if (x * pri[idx] > N) break;
        x *= pri[idx];
        dfs(x, idx + 1, tot * (j + 1), j);
    }
}

int main () {
    scanf("%lld", &N);
    dfs(1, 1, 1, 30);
    printf("%lld\n", res);
    return 0;
}