P2723 [USACO3.1] 丑数 Humble Numbers

题目描述

对于一给定的素数集合 $S = \{ p_1, p_2, ..., p_k \}$, 考虑一个正整数集合,该集合中任一元素的质因数全部属于 $S$。这个正整数集合包括,$p_1$、$p_1 \times p_2$、$p_1 \times p_1$、$p_1 \times p_2 \times p_3$ ...(还有其它)。该集合被称为 $S$ 集合的“丑数集合”。注意:我们认为 $1$不是一个丑数。 你的工作是对于输入的集合 $S$ 去寻找“丑数集合”中的第 $n$ 个“丑数”。保证答案可以用 32 位有符号整数表示。 补充:丑数集合中每个数从小到大排列,每个丑数都是素数集合中的数的乘积,第 $n$ 个“丑数”就是在能由素数集合中的数相乘得来的(包括它本身)第 $n$ 小的数。

输入格式

输出格式

说明/提示

#### 数据规模与约定 对于 $100\%$ 的数据,保证: - $1 \leq k \leq 100$。 - $1 \leq n \leq 10^5$。 - $2 \leq p_i < 2^{31}$,且 $p_i$ 一定为质数。 --- #### 说明 题目翻译来自 NOCOW。 USACO Training Section 3.1