形式化题目

对于正整数 $x$，记 $d(x)$ 为 $x$ 的正约数个数。若对所有满足 $1 \leqslant y < x$ 的正整数 $y$，均有 $d(y) < d(x)$，则称 $x$ 为反素数（Antiprime）。

给定正整数 $n$（$1 \leqslant n \leqslant 2 \times 10^9$），求出满足 $x \leqslant n$ 的最大反素数 $x$。

正解

思路

1. 问题等价转化

反素数要求任何严格小于它的数，约数个数都严格小于它。由此可得出以下两条关键性质：

1. 约数个数最多：在区间 $[1, n]$ 内，不存在任何数的约数个数严格大于最终所求反素数。若存在某个 $y \leqslant n$ 使得 $d(y) > d(x)$，则在区间 $[x+1, n]$ 中必然能找到约数个数超过 $d(x)$ 的数，与 $x$ 是不超过 $n$ 的最大反素数矛盾。
2. 相同约数个数取最小：若有多个数的约数个数相同且达到最大值，反素数必然是其中数值最小的那一个。因为如果选了较大的数 $z > x$ 且 $d(z) = d(x)$，那么根据定义，存在比 $z$ 小的数 $x$ 使得 $d(x) \geqslant d(z)$，则 $z$ 本身就不是反素数。

因此，求不超过 $n$ 的最大反素数，等价于在 $[1, n]$ 中寻找约数个数最多、且数值尽可能小的数。

2. 质因子与指数单调性

根据算术基本定理，任何正整数 $x$ 都可以唯一分解为若干质因子的乘积：

观察约数个数公式可以发现：约数个数只与指数多重集 $\{c_i\}$ 有关，与具体的质数底数无关。 若存在 $i < j$（即质数 $p_i < p_j$）使得指数 $c_i < c_j$，我们只需交换指数 $c_i$ 与 $c_j$，构成新数：

由此得到核心推论：反素数的质因子必由前若干个连续素数构成，且质因子指数单调不增：

3. 搜索范围与剪枝

1. 素数个数上界： 前 10 个素数的乘积为：
   $$2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23 \times 29 = 6{,}469{,}693{,}230 > 2 \times 10^9$$
   因此在 $n \leqslant 2 \times 10^9$ 的范围内，任何候选数最多包含前 10 个素数。
2. 最大指数上界： 因为 $2^{31} > 2 \times 10^9$，所以最小素数 $2$ 的指数 $c_1 \leqslant 30$。
3. DFS 搜索流程： 从最小素数 $2$ 开始按序递归枚举每个素数的指数：
   • 当前素数 $p_{idx}$ 的指数 $c$ 必须满足 $0 \leqslant c \leqslant c_{idx-1}$（保证指数单调不增）；
   • 累乘过程中如果超出 $n$ 则立即剪枝回溯；
   • 遍历完或无法继续乘时，比较当前累积约数个数与全局最优解：优先选择约数个数更大者；约数个数相同时选择数值更小者。

可视化解析

以 $n=1000$ 为例，前几个连续素数为 $[2, 3, 5, 7, 11]$。搜索树只在非递增指数序列上展开，候选形态如下表所示：

状态转移逻辑如下图所示：

graph TD
    Root["开始搜索: DFS(p_idx=0, max_exp=31, num=1, divs=1)"]
    Root --> Choose2["枚举 2 的指数 c1 (1..30)"]
    Choose2 --> Choose3["枚举 3 的指数 c2 (1..c1)"]
    Choose3 --> Choose5["枚举 5 的指数 c3 (1..c2)"]
    Choose5 --> Dots["... 依序枚举后继质数"]
    Dots --> Check["更新最优解: divs > best_divs 或 (divs == best_divs 且 num < best_num)"]

代码

Python 版：

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 22:45
# update_at: 2026-09-30 22:45

import sys

# 前 10 个质数连乘已经超过 2*10^9 (2*3*5*...*29 = 6469693230 > 2*10^9)
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]


def search(p_idx: int, max_exp: int, num: int, divs: int, bound: int, best: list[int]) -> None:
    """递归搜索质因子指数不增的候选数，维护约数最多且数值最小的解。

    best 结构：[best_num, max_divs]
    """
    better_divs = divs > best[1]
    same_divs_smaller = divs == best[1] and num < best[0]
    if better_divs or same_divs_smaller:
        best[0], best[1] = num, divs

    if p_idx == len(PRIMES):
        return

    p = PRIMES[p_idx]
    cur = num
    for exp in range(1, max_exp + 1):
        cur *= p
        if cur > bound:
            break
        search(p_idx + 1, exp, cur, divs * (exp + 1), bound, best)


def max_antiprime(n: int) -> int:
    """计算不大于 n 的最大反素数。"""
    best = [1, 1]  # [best_number, max_divisors]
    search(0, 31, 1, 1, n, best)
    return best[0]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    print(max_antiprime(n))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 23:10
 * update_at: 2026-10-05 23:10
 */

#include <cstdio>

typedef long long ll;

const int PNUM = 10; // n <= 2*10^9，前 10 个质数连乘 6469693230 已超界，最多用到第 10 个质数

// 前若干个质数：反素数的质因子必由连续前缀质数构成
ll pri[PNUM + 1] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

ll n;       // 题目给定的上界
ll best_num = 1;  // 当前最优反素数（约数最多，同约数个数时数值最小）
ll best_divs = 1; // 当前最优反素数的约数个数

// 按序枚举第 idx 个质数的指数 exp：1..max_exp（指数单调不增的剪枝）
// num：当前累积的数；divs：当前约数个数（各 (指数+1) 的乘积）
void dfs(ll idx, ll max_exp, ll num, ll divs) {
    // 每个节点都是一个候选数：约数更多者优先，约数相同取数值更小者
    if (divs > best_divs || (divs == best_divs && num < best_num)) {
        best_num = num;
        best_divs = divs;
    }

    if (idx > PNUM) return; // 质数用尽

    ll cur = num;
    // 这一层在选择第 idx 个质数的指数，指数不能超过上一层的 max_exp
    for (ll e = 1; e <= max_exp; ++e) {
        cur *= pri[idx];
        if (cur > n) break; // 超过 n，再乘只会更大，剪枝回溯
        dfs(idx + 1, e, cur, divs * (e + 1));
    }
}

int main() {
    scanf("%lld", &n);
    // 初始约数个数上界 31：2^31 > 2*10^9，质数 2 的指数最多 30
    dfs(1, 31, 1, 1);
    printf("%lld\n", best_num);
    return 0;
}

复杂度

• 时间复杂度：满足 $\prod_{i=1}^k p_i^{c_i} \leqslant 2 \times 10^9$ 且 $c_1 \geqslant c_2 \geqslant \dots$ 的搜索状态数极其有限（合法状态总数不足几千个）。DFS 实际访问节点极少，运行耗时低于 $0.03\text{ s}$。
• 空间复杂度：递归深度不超过质数个数（最多 10 层），空间复杂度为 $O(1)$。

总结

反素数的核心在于将题目要求的“小于它的数约数个数均严格小于它”转化为“在 $[1, n]$ 中求约数最多、数值最小的正整数”。再通过因数个数公式中底数与指数的对称性，利用反证法推导得出“质因子底数必为连续前缀素数且指数单调不增”。利用这一强剪枝条件，庞大的枚举空间被压缩到极小的规模，直接 DFS 即可在极短时间内得出正解。