#262. 丑数

丑数

题目描述

对于一给定的素数集合 S={p1,p2,...,pk}S = \{ p_1, p_2, ..., p_k \}, 考虑一个正整数集合,该集合中任一元素的质因数全部属于 SS。这个正整数集合包括,p1p_1p1×p2p_1 \times p_2p1×p1p_1 \times p_1p1×p2×p3p_1 \times p_2 \times p_3 ...(还有其它)。该集合被称为 SS 集合的“丑数集合”。注意:我们认为 11不是一个丑数。

你的工作是对于输入的集合 SS 去寻找“丑数集合”中的第 nn 个“丑数”。

补充:丑数集合中每个数从小到大排列,每个丑数都是素数集合中的数的乘积,第 nn 个“丑数”就是在能由素数集合中的数相乘得来的(包括它本身)第 nn 小的数。

输入格式

输入的第一行是两个的整数,分别代表集合 SS 的大小 kk 和给定的参数 nn

输入的第二行有 kk 互不相同的整数,第 ii 个整数代表 p_i。

输出格式

输出一行一个整数,代表答案。

4 19
2 3 5 7
27

数据范围

对于 100%100\% 的数据,保证:

  • 1k1001 \leq k \leq 100
  • 1n1051 \leq n \leq 10^5
  • 2pi<2312 \leq p_i < 2^{31},且 pip_i 一定为质数。