humble_USACO

Humble Numbers

For a given set of K prime numbers S = {p, p, ..., p}, consider the set of all numbers whose prime factors are a subset of S. This set contains, for example, p, pp, pp, and ppp (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)

题意：对于一给定的素数集合 S = {p, p, ..., p},考虑一个正整数集合，该集合中任一元素的质因数全部属于S。这个正整数集合包括，p、p*p、p*p、p*p*p...(还有其它)。该集合被称为S集合的“丑数集合”。

注意：我们认为1不是一个丑数。

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

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

/*

ID: LinKArftc

PROG: humble

LANG: C++

*/

#include <map>

#include <set>

#include <cmath>

#include <stack>

#include <queue>

#include <vector>

#include <cstdio>

#include <string>

#include <utility>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define eps 1e-8

#define randin srand((unsigned int)time(NULL))

#define input freopen("input.txt","r",stdin)

#define debug(s) cout << "s = " << s << endl;

#define outstars cout << "*************" << endl;

const double PI = acos(-1.0);

const int inf = 0x3f3f3f3f;

const int INF = 0x7fffffff;

typedef long long ll;

const int maxn = ;

const int maxm = ;

ll num[maxm], ri[maxm], ans[maxn];

int k, n;

int main() {

    freopen("humble.in", "r", stdin);

    freopen("humble.out", "w", stdout);

    int tot = ;

    scanf("%d %d", &n, &k);

    for (int i = ; i < n; i ++) scanf("%lld", &num[i]);

    ans[tot ++] = ;

    memset(ri, , sizeof(ri));

    while (tot < k + ) {

        int ii;

        ll mi = 0x7fffffffffffffff;

        for (int i = ; i < n; i ++) {

            while (num[i] * ans[ri[i]] <= ans[tot-]) ri[i]++;

            if (num[i] * ans[ri[i]] < mi) {

                mi = num[i] * ans[ri[i]];

                ii = i;

            }

        }

        ans[tot++] = mi;

        ri[ii] ++;

    }

    printf("%lld\n", ans[k]);

    return ;

}