bzoj 1053 反素数

阅读量: searchstar 2019-11-04 23:44:48
Categories： Tags：

题目大意：定义，当任意小于x的数的约数的个数都小于x的约数的个数时，称x为反素数。
给定n <= 2e9，求小于等于n的最大的反素数。

感觉以前刷数学刷偏了。这么简单的题都不会。。。
显然，当两个小于等于n的数的因子数相同时，较小的那个数才是反素数（之前就是这里没发现）。而因子数等于这个数的质因数展开式的各个幂+1之积，所以显然质因数越小越好，因为越小幂就会越大，而且越小这个数的值也越小。所以我们暴力枚举前10个素数的幂（用dfs剪一下枝），然后取因子数最大时的最小值即可。

代码：

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;

int n;

const int len = 10;
const int ps[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int mx, x;
void dfs(int d, int now, int num) {
    if (len == d) {
        if (num > mx) {
            mx = num;
            x = now;
        } else if (num == mx) {
            x = min(x, now);
        }
    } else {
        for (int cnt = 0; ; ++cnt) {
            dfs(d + 1, now, num * (cnt + 1));
            LL tmp = (LL)now * ps[d];
            if (tmp > n) break;
            else now = tmp;
        }
    }
}
int main() {
    scanf("%d", &n);
    mx = x = -1;
    dfs(0, 1, 1);
    printf("%d", x);

    return 0;
}

2019 CCPC 哈尔滨站 B题
bzoj 1502月下柠檬树 Simpson积分