humble_USACO

Humble Numbers

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

题意：对于一给定的素数集合 S = {p₁, p₂, ..., p_K},考虑一个正整数集合，该集合中任一元素的质因数全部属于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 = 100010;
const int maxm = 110;

ll num[maxm], ri[maxm], ans[maxn];
int k, n;

int main() {
    freopen("humble.in", "r", stdin);
    freopen("humble.out", "w", stdout);
    int tot = 0;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i ++) scanf("%lld", &num[i]);
    ans[tot ++] = 1;
    memset(ri, 0, sizeof(ri));
    while (tot < k + 1) {
        int ii;
        ll mi = 0x7fffffffffffffff;
        for (int i = 0; i < n; i ++) {
            while (num[i] * ans[ri[i]] <= ans[tot-1]) ri[i]++;
            if (num[i] * ans[ri[i]] < mi) {
                mi = num[i] * ans[ri[i]];
                ii = i;
            }
        }
        ans[tot++] = mi;
        ri[ii] ++;
    }
    printf("%lld
", ans[k]);

    return 0;
}