For a given set of K prime numbers S = {p1, p2, ..., pK}, consider the set of all numbers whose prime factors are a subset of S. This set contains, for example, p1, p1p2, p1p1, and p1p2p3 (among others). This is the set of `humble numbers' for the input set S. Note: The number 1 is explicitly declared not to be a humble number.
Your job is to find the Nth humble number for a given set S. Long integers (signed 32-bit) will be adequate for all solutions.
PROGRAM NAME: humble
INPUT FORMAT
Line 1: | Two space separated integers: K and N, 1 <= K <=100 and 1 <= N <= 100,000. |
Line 2: | K space separated positive integers that comprise the set S. |
SAMPLE INPUT (file humble.in)
4 19 2 3 5 7
OUTPUT FORMAT
The Nth humble number from set S printed alone on a line.
SAMPLE OUTPUT (file humble.out)
27
题意:
给出 N(1 ~ 100)个素数 和 K (1 ~ 100000)。输出第 K 个数,这个数的质因子只能由这 N 个里面的数组成。规定 1 不算入其中。
思路:
技巧。与第二次个人排位赛素数筛选那道题类似,为了方便计算,所以把 1 也算入其中。用数组 hum 记录前 100000 个数( hum 数组绝对是从小到大排序的 ),更新的时候只需要更新到 K 为止。对于每一个素数 num[ i ] 对应都有一个下标值 fir [ i ]。当需要更新第 j 个 hum 时,每个一个素数都要找到第一个 fir [ i ] 满足 num [ i ] * hum [ fir [ i ] ] > hum [ j - 1 ] ,同时比较取得每个素数 num [ i ] * hum [ fir [ i ] ] 的最小值,这个最小值即为 hum [ j ] 的值。如此更新下去,最后输出 hum [ k ] 即可。
AC:
/* TASK:humble LANG:C++ ID:sum-g1 */ #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const ll INF = 999999999999; ll num[105], fir[105]; ll hum[100005]; int main() { freopen("humble.in", "r", stdin); freopen("humble.out", "w", stdout); int n, k; scanf("%d%d", &n, &k); for (int i = 1; i <= n; ++i) { scanf("%lld", &num[i]); fir[i] = 0; } hum[0] = 1; for (int i = 1; i <= k; ++i) { ll Min = INF; for (int j = 1; j <= n; ++j) { while (num[j] * hum[ fir[j] ] <= hum[i - 1]) ++fir[j]; if (num[j] * hum[ fir[j] ] < Min) Min = num[j] * hum[ fir[j] ]; } hum[i] = Min; } printf("%lld\n", hum[k]); return 0; }
相关推荐
Humble Numbers 一道简单DP题
ros humble的key
The Humble Programmer,当年图灵奖的演技录
1972图灵奖获得者Edsger W. Dijkstra讲稿
com.humble.SlayTheSpire.apk
Python脚本提取所有Humble键并自动在Steam上赎回它们。 这主要是设计成一种“设置后忘”的工具,可以最大程度地成功将密钥输入Steam,从而确保不会赎回Steam游戏。 该脚本将同时登录Humble和Steam,从而使整个过程...
Humble是一组松散耦合的工具,旨在使用go和构建客户端和混合Web应用程序。 Humble专为编写前端代码而设计,完全与后端无关。 您可以将Humble与以任何语言编写的任何后端服务器结合使用。 如果您确实选择同时编写...
如果使用Maven,则将Humble部署到Maven中央存储库。 要将其包含在您的项目中(请注意:这将包括所有操作系统的工件),请将其添加到pom.xml中: ... ... < groupId>io.humble < artifactId>humble-video-...
如果您有兴趣签出最新的书籍捆绑包(如果有),只需单击Humble Bundle主页顶部的“书籍捆绑包”标签。 例如常规捆绑包,将有多个层次。 顶层将显示可用于“按需支付”的内容。 下面是“超越平均水平”(绿色)层,...
从Humble Bundle库中下载所有内容! 第一次运行可能需要一段时间,因为它将下载所有内容。 之后,它将仅下载已更新或丢失的内容。 产品特点 支持Humble Trove (-- --trove标志) 每次运行时从您的Humble Bundle...
资源来自pypi官网。 资源全名:humble-0.1.2.tar.gz
Humble Key Restriction 描述 查看 Humble Bundle Key 的激活激活限制插件 它能帮你在 Humble 的 Download 界面显示 Key 的激活限制信息。 安装 安装 (推荐)、 或者其它用户脚本管理工具 安装脚本 就可以用啦 XD ...
做的很辛苦, 里面附有注释,大家支持一下吧...
从HUMBLE买的的unity开发进阶书籍慈善包,包含untiy性能优化,shader,C#,项目实例,企业增强现实项目,Unity认证程序员:考试指南等等。进阶高级开发必备书籍(但是注意一点,是全英文)
谦逊的 谦虚是一个简单的图形约简引擎。 我的意思很简单。 基本上是应用于图的规则列表。 规则使用我能想到的最简单的模式匹配算法,将其天真地转换为if语句。 规则可以延迟应用; 仅在最高级别,并且由规则决定,...
Humble Trove下载器 快速而肮脏的脚本,用于从下载适用于所有操作系统的所有游戏。 您需要订阅Humble Monthly才能下载这些游戏。 现有文件的md5校验和与Humble Bundle API报告的内容进行了比较。 如果不匹配,则...
Humble_Pal Humble Pal 通过自动化和跟踪扩展了 Humble Bundle 的功能。
谦虚捆绑(非官方)API只是Humble Bundle的非官方API为什么? 实际上有两个主要原因。 首先,可能也是最重要的一个,这是Telegram上的后端。 第二个原因是因为我想研究微服务,所以我将通道背后的逻辑分为模块,这...
hb下载器自动化实用程序,用于下载您的Humble Bundle产品 http://www.humblebundle.com该软件包未得到Humble Bundle,Inc.的认可,支持或关联。 它是根据MIT许可分发的,如果您同意该许可的条款,则可以免费使用,...
最基础的DP题目解题报告,适合初学者!动态规划(DP1) ...解题报告: 1001 计算直线的交点数 1002 FatMouse's Speed1003 Common ... 1006 免费馅饼 1007 Humble Numbers1008 Monkey and Banana 1009 龟兔赛跑 1010 数塔