/ Vijos / 题库 /

第k小分数

第k小分数

时间限制:1秒  内存限制:256M


【题目描述】

  给定 \(N\) 个不同的质数 \(P_1, P_2, ..., P_N\)。用它们作为分母可以组成 \((P_1-1) + (P_2-1) + ... (P_N-1)\) 个分数:
  \(1/P_1, 2/P_1, 3/P_1, ..., (P_1-1)/P_1, 1/P_2, 2/P_2, 3/P_2, ... (P_2-1)/P_2, ... 1/P_N, 2/P_N, ... (P_N-1)/P_N\)

  请帮助小Ho求出其中第 \(K\) 小的分数。

【输入格式】

  第一行包含两个整数 \(N\) 和 \(L\)。
  以下 \(N\) 行每行包含一个质数 \(P_i\)。

【输出格式】

  输出一个分数表示答案

【输入输出样例】

 Input

3 4  
2  
3  
5

 Output

1/2

【数据限制】

  对于 \(70\%\) 的数据,\(1≤N≤100\),\(1≤K≤1000000\),\(2≤P≤100000\)。
  对于 \(100\%\) 的数据,\(1≤N≤1000\),\(1≤K≤1000000000\),\(2≤P≤1000000000\)。

【来源】

  Mr.he

信息

ID
2307
难度
(无)
分类
枚举搜索 | 枚举其他 | 二分查找 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
1
上传者