1625：【例 1】反素数 Antiprime

题目描述

如果一个大于等于 $1$ 的正整数 $n$，满足所有小于 $n$ 且大于等于 $1$ 的所有正整数的约数个数都小于 $n$ 的约数个数，则 $n$ 是一个反素数。譬如：$1,2,4,6,12,24$，它们都是反素数。

请你计算不大于 $n$ 的最大反素数。

输入格式

一行一个正整数 $n$。

输出格式

只包含一个整数，即不大于 $n$ 的最大反素数。

样例

样例输入 #1

1000

样例输出 #1

840

样例解释 #1

• 反素数的定义：对于任意 $m < n$，$d(m) < d(n)$，其中 $d(x)$ 表示 $x$ 的约数个数。
• 在不超过 $1000$ 的范围内，最大的反素数是 $840$。
• 验证：$840$ 的约数个数为 $32$（因为 $840 = 2^3 \times 3 \times 5 \times 7$，约数个数 $(3+1)(1+1)(1+1)(1+1)=4 \times 2 \times 2 \times 2=32$）。小于 $840$ 的数中，约数个数最多的是 $720$（有 $30$ 个约数）等，都小于 $32$。

数据范围

• 对于 $10\%$ 的数据，$1 \le n \le 10^3$；
• 对于 $40\%$ 的数据，$1 \le n \le 10^6$；
• 对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^9$。

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：反素数就是在一定范围内约数个数最多的数中最小的那个。因为如果 $n$ 是反素数，那么对于所有 $m < n$，都有 $d(m) < d(n)$，这意味着 $n$ 是第一个达到这个约数个数的数，即 $n$ 是拥有该约数个数的最小数。因此，问题转化为：在不超过 $n$ 的范围内，找到约数个数最多的数，如果有多个，取最小的那个（即反素数）。

由于 $n$ 最大 $2 \times 10^9$，直接枚举每个数求约数个数不可行。注意到一个数的约数个数由其质因数分解决定。设 $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$，则 $d(n) = (a_1+1)(a_2+1)\cdots(a_k+1)$。为了在不超过 $n$ 的前提下使 $d(n)$ 最大，我们需要选择较小的质数（如 $2,3,5,7,11,\dots$）且指数 $a_i$ 递减（即 $a_1 \ge a_2 \ge \dots \ge a_k$），因为较小的质数贡献更大。可以使用 DFS 搜索，枚举每个质数的指数，生成所有可能的候选数，记录约数个数最多的最小数。由于质数乘积增长很快，搜索深度有限（前 $10$ 个质数乘积已超过 $2\times 10^9$），可以剪枝。

算法步骤：

1. 预处理前若干个质数（例如前 $10$ 个质数：$2,3,5,7,11,13,17,19,23,29$）。
2. DFS 搜索，参数包括：当前质数下标、上一个质数的指数、当前乘积、当前约数个数。
3. 限制：乘积不超过 $n$，指数非递增（即当前质数的指数不超过上一个质数的指数）。
4. 如果当前约数个数大于记录的最大约数个数，或相等但当前乘积更小，则更新答案。
5. 搜索所有可能组合。

最终答案即为所求。