常见的网站开发工具有哪些/百度怎么找人工客服

1. 问题描述：

对于任何正整数 x，其约数的个数记作 g(x)，例如 g(1) = 1、g(6) = 4。如果某个正整数 x 满足：对于任意的小于 x 的正整数 i，都有 g(x) > g(i)，则称 x 为反素数。例如，整数 1，2，4，6 等都是反素数。现在给定一个数 N，请求出不超过 N 的最大的反素数。

输入格式

一个正整数 N。

输出格式

一个整数，表示不超过 N 的最大反素数。

数据范围

1 ≤ N ≤ 2 ∗ 10 ^ 9

输入样例：

1000

输出样例：

840
来源：https://www.acwing.com/problem/content/description/200/

2. 思路分析：

我们可以先想一下1~N中最大的反素数是哪一个，可以发现是约数个数最多并且是最小的那个数字，因为当约数约数相同的时候那么只有最左边的数字才是满足要求的，直接做好像不是特别好做，所以可以想一下有什么性质，可以发现2 * 10 ^ 9的质因子的个数并不是特别多，2 * 3 * 5 ... = 2 * 10 ^ 9，最多在23就超过2 * 10 ^ 9了，总共会使用到的质因子的个数最多有9个：

• 不同质因子的个数最多有9个
• 每个质因子的最大个数为30（2 ^ 31 > 2 * 10 ^ 9）
• 所有质因子的个数是依次递减的

根据这些特点可以发现数据规模非常小，所以我们可以使用dfs来解决，使用dfs枚举满足上面性质的约数个数最多并且是最小的那个数字。

3. 代码如下：

from typing import Listclass Solution:# maxd记录出现的质因子的最大次数, num记录满足要求的数字maxd = num = 0# u表示当前递归的位置, last表示当前质因子出现的次数, p表示当前质因子相乘得到的数字, s表示质因子的个数def dfs(self, u: int, last: int, p: int, s: int, n: int, primes: List[int]):# 需要求解的是约数个数最多并且是最小的那个, 因为当约数相等的时候若当前的p更小那么需要更新numif self.maxd < s or (s == self.maxd and p < self.num):self.maxd = sself.num = pif u == 9: returnfor i in range(1, last + 1):if primes[u] * p > n: break# p乘以对应的质因子p *= primes[u]self.dfs(u + 1, i, p, s * (i + 1), n, primes)# 使用暴搜来解决def process(self):# 在2 ∗ 10 ^ 9之内最多可以到23primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]n = int(input())self.maxd = self.num = 0self.dfs(0, 30, 1, 1, n, primes)return self.numif __name__ == '__main__':print(Solution().process())