P2723 丑数 Humble Numbers

    • 1.3K通过
    • 4.2K提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 平衡树 排序 搜索 数论,数学 枚举,暴力 USACO
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    对于一给定的素数集合 S = {p1, p2, ..., pK},考虑一个正整数集合,该集合中任一元素的质因数全部属于S。这个正整数集合包括,p1、p1*p2、p1*p1、p1*p2*p3...(还有其它)。该集合被称为S集合的“丑数集合”。注意:我们认为1不是一个丑数。

    题目描述

    你的工作是对于输入的集合S去寻找“丑数集合”中的第N个“丑数”。所有答案可以用longint(32位整数)存储。

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

    输入输出格式

    输入格式:

    第 1 行: 二个被空格分开的整数:K 和 N , 1<= K<=100 , 1<= N<=100,000.

    第 2 行: K 个被空格分开的整数:集合S的元素

    输出格式:

    单独的一行,输出对于输入的S的第N个丑数。

    输入输出样例

    输入样例#1: 复制
    4 19
    2 3 5 7
    输出样例#1: 复制
    27

    说明

    题目翻译来自NOCOW。

    USACO Training Section 3.1

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。