洛谷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：

说明

题目翻译来自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
", 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
", 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
", hum[n]);
    return 0;
}