首页 > 代码库 > 洛谷P2723 丑数 Humble Numbers
洛谷P2723 丑数 Humble Numbers
P2723 丑数 Humble Numbers
- 52通过
- 138提交
- 题目提供者该用户不存在
- 标签USACO
- 难度普及/提高-
讨论 题解
最新讨论
- 暂时没有讨论
题目背景
对于一给定的素数集合 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个丑数。
输入输出样例
4 192 3 5 7
27
说明
题目翻译来自NOCOW。
USACO Training Section 3.1
分析：一开始的思路是先把很多丑数求出来，然后排个序，输出第n个，但是由于n太大，而且没有范围，所以不行.
优化一下，求出了第i-1个丑数，把所有可能的第i个丑数求出来，放到优先队列中，然后弹出最小的，这样的话要涉及到判重，TLE.
换一种思路，为了找第i个丑数，那么一定要比第i-1个丑数大，而且是最小的那一个，打个表，可以发现比i-1大的丑数一定是比i-1小的丑数乘某个质数得到的，鉴于质数的数量很少，而丑数的数量很大，我们枚举质数，然后枚举丑数，直到大于第i-1个丑数，记录一下，找到所有的符合条件的丑数以后，找出最小值（也可以在寻找的途中更新最小值），那么这个最小值就是第i个丑数，不会超时.
51分代码：
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <map>#include <set>#include <queue>#include <functional>int k, n;long long s[110], ans[100010], tot;set <long long> m;priority_queue <long long, vector<long long>, greater<long long> >q;int main(){ scanf("%d%d", &k, &n); for (int i = 1; i <= k; i++) { scanf("%lld", &s[i]); q.push(s[i]); } //q.push(1); while (tot <= n) { long long x = q.top(); q.pop(); //printf("%d\n", x); if (!m.count(x)) { ans[++tot] = x; m.insert(x); } for (int i = 1; i <= k; i++) q.push(s[i] * x); printf("%d\n", tot); } printf("%lld", ans[n]); //while (1); return 0;}
AC代码：
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <map>#include <set>#include <queue>#include <functional>int pindex[110];int prime[110];int count;long long hum[1000001];int main(void){ int k, n; int i; int min, m; scanf("%d%d", &k, &n); for (i = 1; i <= k; i++) { scanf("%d", &prime[i]); } hum[count++] = 1; memset(pindex, 0, sizeof(pindex)); while (count <= n) { min = 0x7FFFFFFF; for (i = 1; i <= k; i++) { while (prime[i] * hum[pindex[i]] <= hum[count - 1]) { pindex[i]++; } if (prime[i] * hum[pindex[i]] < min) min = prime[i] * hum[pindex[i]]; } hum[count++] = min; } printf("%lld\n", hum[n]); return 0;}
洛谷P2723 丑数 Humble Numbers