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

sys_con

高一 OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注