「HAOI2007」反素数 - 数论 + DFS

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

LibreOJ 链接

对于任何正整数 \(x\)，其约数的个数记作 \(g(x)\)。例如 \(g(1) = 1\)，\(g(6) = 4\)。

如果某个正整数 \(x\) 满足：\(\forall 0 < i < x\)，都有 \(g(x) < g(i)\)，则称 \(x\) 为反质数。例如，整数 \(1, 2, 4, 6\) 等都是反质数。

现在给定一个数 \(N\)，你能求出不超过 \(N\) 的最大的反质数么？

数据范围：\(1 \leq N \leq 2 \times 10^9\)

解题思路

数学证明

首先我们有如下结论：

  1. 小于等于 \(N\) 的最大反质数为约数个数中多的数中最小的一个。

  2. 小于等于 \(N\) 的不同的质因数个数都不会超过 \(10\)，且所有质因数个数的和不超过 \(30\)。

  3. 若 \(x\) 为反质数，则 \(x\) 必定满足： \[ \begin{cases} x = 2^{p_1} \times 3^{p_2} \times 5^{p_3} \times 7^{p_4} \times 11^{p_5} \times 13^{p_6} \times 17^{p_7} \times 19^{p_8} \times 23^{p_9} \times 29^{p_{10}} \\ p_1 \geq p_2 \geq p_3 \geq \cdots \geq p_{10} \geq 0 \end{cases} \]

接下来为证明：

  1. 对于结论 \(1\)，我们设 \(x\) 为约数最多的数中最小的一个。则有以下结论：

    1. \(\forall y < x \Rightarrow g(y) < g(x)\)，即 \(x\) 为反质数。

    2. \(\forall y > x \Rightarrow g(y) \leq g(x)\)，即大于 \(x\) 的数都不为反质数。

  2. 对于结论 \(2\)，显然 \(2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23 \times 29 \times 31> 2 \times 10^9\)， 故不可能会有拥有超过 \(10\) 个不同的质因数的数小于等于 \(2 \times 10^9\)。且 \(2 ^ {31} > 2 \times 10^9\)，故小于 \(2 \times 10^9\) 的数的质因数个数不可能大于 \(30\)。

  3. 对于结论 \(3\)，我们可以使用反证法。设 \(x\) 为反质数且满足 \(i < j\) 且 \(p_i > p_j\)，则令 \(y\) 的 \(p_i\) 项比 \(x\) 的 \(p_i\) 多 \(1\)，\(y\) 的 \(p_j\) 项比 \(x\) 的 \(p_j\) 少 \(1\)，\(p\) 的其余项相等。显然 \(x < y\) 且 \(g(x) = g(y)\)，\(x\) 不为反质数，故矛盾，原结论成立。

DFS

接下来我们可以设最大反质数为:

\[ x = 2^{p_1} \times 3^{p_2} \times 5^{p_3} \times 7^{p_4} \times 11^{p_5} \times 13^{p_6} \times 17^{p_7} \times 19^{p_8} \times 23^{p_9} \times 29^{p_{10}} \]

通过 DFS 枚举 \(p\) 数组的所有情况。时间复杂度小于 \(O(n)\)。

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <cstring>
#include <iostream>

long long n;
int p[10], pAns[10], m[10] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 };

long long power(long long a, int b) {
    long long ans = 1;
    while (b > 0) {
        if ((b & 1) == 1) {
            ans *= a;
        }
        a *= a;
        b >>= 1;
    }
    return ans;
}

long long calcP(int end) {
    long long ans = 1;
    for (int i = 0; i < end; i++) ans *= power(m[i], p[i]);
    return ans;
}

long long sumP() {
    long long ans = 1;
    for (int i = 0; i < 10; i++) ans *= p[i] + 1;
    return ans;
}

long long calcAns(int end) {
    long long ans = 1;
    for (int i = 0; i < end; i++) ans *= power(m[i], pAns[i]);
    return ans;
}

long long sumAns() {
    long long ans = 1;
    for (int i = 0; i < 10; i++) ans *= pAns[i] + 1;
    return ans;
}

void dfs(int step) {
    if (step >= 10) {
        if (sumP() >= sumAns()) {
            if (sumP() > sumAns()) memcpy(pAns, p, sizeof(p));
            else if (calcP(10) < calcAns(10)) memcpy(pAns, p, sizeof(p));
        }
        return;
    }

    long long maxn = calcP(step), before = step == 0 ? (long long) 2e9 : p[step - 1];

    for (long long i = 0; power(m[step], i) * maxn <= n && i <= before; i++) {
        p[step] = i;
        dfs(step + 1);
    }
}

int main() {
    std::cin >> n;

    memset(p, 0, sizeof(p));
    memset(pAns, 0, sizeof(pAns));
    dfs(0);

    std::cout << calcAns(10) << std::endl;

    return 0;
}