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个丑数。
输入输出样例
输入样例#1：
4 19
2 3 5 7
输出样例#1：
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[], ans[], 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 = ; 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 = ; i <= k; i++)
q.push(s[i] * x);
printf("%d\n", tot);
}
printf("%lld", ans[n]);
//while (1); return ;
}
AC代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <functional>
int pindex[];
int prime[];
int count;
long long hum[]; int main(void)
{
int k, n;
int i;
int min, m;
scanf("%d%d", &k, &n);
for (i = ; i <= k; i++) {
scanf("%d", &prime[i]);
}
hum[count++] = ;
memset(pindex, , sizeof(pindex));
while (count <= n) {
min = 0x7FFFFFFF;
for (i = ; i <= k; i++) {
while (prime[i] * hum[pindex[i]] <= hum[count - ]) {
pindex[i]++;
} if (prime[i] * hum[pindex[i]] < min)
min = prime[i] * hum[pindex[i]];
}
hum[count++] = min;
} printf("%lld\n", hum[n]);
return ;
}