Humble Numbers

For a given set of K prime numbers S = {p1, p2, ..., pK}, consider the set of all numbers whose prime factors are a subset of S. This set contains, for example, p1, p1p2, p1p1, and p1p2p3 (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

题意：
在给出的素数中N[i]（humble numbers），取若干个数相乘可以产生其他humble number。求humbel number按大小排序后的第n个数。

可以按小到大生成n个humble numbers存在s数组中。所有的humble number都是有给出的素数因子相乘得出的。对每个素数，附上一
个变量index[i]，表示下次要乘上N[i]的数在s中的下标。则s[j]可以通过min(N[i] * s[index[i]])（i from 0 to k - 1）求得。然后
对于每一个N[i] * index[i] = s[j]的要index[i]++；因为s[i]以算过，对于N[i]的下一个更大的数肯定大于s[i]且在N[i] * s[index[i + 1]]内。

代码如下：


/*
LANG: C
TASK: humble
*/
#include<stdio.h>
#define nmax 100000
struct N
{
    int x, index;
}N[100];
int F[100], s[nmax]; 
int FindIndex(int n)
{
    int i, pre, index;    
    pre = F[0] = N[0].x * s[N[0].index], index = 0;
    for (i = 1; i < n; i++)
    {
        F[i] = N[i].x * s[N[i].index]; //求下一个humble number 
        if (pre > F[i])
        {
            pre = F[i], index = i;
        }
    }
    for (i = 0; i < n; i++)
    {
        if (F[i] == pre)//对于相乘只为pre的素数因子的小标自加。 
        {
            N[i].index++;
        }
    }
    return index;
}        
int main()
{
    freopen("humble.in", "r", stdin);
    freopen("humble.out", "w", stdout);
    int n, m, i, index;
    scanf("%d%d", &n, &m);
    for (i = 0; i < n; i++)
    {
        scanf("%d", &N[i].x);
        N[i].index = 0;//初始下标是0.因为s[0] = 1，第一个最小的数就是给出的数中的最小值 
    }
    s[0] = 1;
    for (i = 1; i <= m; i++)
    {
        index = FindIndex(n);
        s[i] = F[index];
    }
    printf("%d\n", s[m]);
    fclose(stdin);
    fclose(stdout);
    //system("pause");
    return 0;
}