Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


「HAOI2007」反素数 - 搜索

对于任何正整数 x x ,其约数的个数记作 g(x) g(x) ,例如 g(1)=1 g(1) = 1 g(6)=4 g(6) = 4 。如果某个正整数 x x 对于任何 i(0,x) i \in (0, x) 都满足 g(x)>g(i) g(x) > g(i) ,则称 x x 为反质数。

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

链接

BZOJ 1053

题解

一个反质数 x x 一定是 [1,x] [1, x] 内约数个数最多的数,并且不存在一个 y<x y < x 使 y y 的约数个数与 x x 的相等。

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

x x 的唯一分解式为 x=2t1×3t2××pktk x = 2 ^ {t_1} \times 3 ^ {t_2} \times \ldots \times p_k ^ {t_k} 。则 x x 的约数个数 g(x)=i=1kti g(x) = \prod\limits_{i = 1} ^ k t_i 。假设存在一个 j j 满足 pj p_j pj+1 p_{j + 1} 不是连续的质数,则令 pj+1 p_{j + 1} pj p_j 的下一个质数,pj+2pk p_{j + 2} \sim p_k 向后顺延,这样得到的唯一分解式中,{ti} \{ t_i \} 不变,而 x x 变小了。上述推论得证。

所以,本题的答案的质因子一定是前若干个质数,通过计算可知,前 11 11 个质数({2,3,5,7,11,13,17,19,23,29,31} \{ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 \} )的积大于 2×109 2 \times 10 ^ 9

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

代码

#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;
}
最近的文章

「HAOI2008」移动玩具 - 状态压缩 + BFS

在一个 4×4 4 \times 4 的方框内摆放了若干个相同的玩具,要将这些玩具重新摆放成为理想的状态,规定移动时只能将玩具向上下左右四个方向移动,并且移动到的位置不能有玩具,求最小移动次数。

于  BFS, BZOJ, HAOI, 状态压缩 继续阅读
更早的文章

「HAOI2007」覆盖问题 - 二分答案 + 枚举

用三个 L×L L \times L 的正方形覆盖一些点,使最大正方形的边长最小。

于  BZOJ, HAOI, 二分答案, 枚举 继续阅读
comments powered by Disqus