Humble Numbers - USACO 3.1.3

humblenumbers - codetrick
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

要求是使用给定的一组质数为基，生成一组数，求生成数从小到大排序后的第n个元素。其中质数至多有100个，求的元素至多第是10,000个。

如给定的质数是{2,3,5}，则生成的数组为{2,3,2*2,5,2*3,2*2*2,3*3,2*5….}
https://github.com/antonio081014/USACO-Training/blob/master/ch3_1/humble.java
https://github.com/TomConerly/Competition-Programming/blob/master/USACO/Chapter3/humble.java

	static int solve2(int[] nums, int N ,int K) {
	int[] hum = new int[N+1];
	int[] next = new int[K];
	hum[0] = 1;
	for(int i = 1; i <= N;i++)
	{
	int best = Integer.MAX_VALUE;
	for(int j = 0; j < K;j++)
	{
	while(next[j] < i && nums[j]*hum[next[j]] <= hum[i-1])
	{
	next[j]++;
	}
	best = min(best,nums[j]*hum[next[j]]);
	}
	hum[i] = best;
	}
	return hum[N];
	}

https://github.com/lklein/usaco-training/blob/master/usaco/humble/humble.java

	public long solve(int n, long[] primes) {
	ArrayList<Long> humbles = new ArrayList<Long>();
	humbles.add(1L);
	// This is key
	int[] cursor = new int[primes.length];
	while (humbles.size() < n + 1) {
	long newMin = Long.MAX_VALUE;
	for (int j = 0; j < primes.length; j++) {
	newMin = Math.min(primes[j] * humbles.get(cursor[j]), newMin);
	}
	humbles.add(newMin);
	for (int j = 0; j < primes.length; j++) {
	while (primes[j] * humbles.get(cursor[j]) <= newMin) {
	cursor[j]++;
	}
	}
	}
	return humbles.get(n);
	}

http://sdjl.me/index.php/archives/117

    private static void run()
    {
        //为了计算方便，我们认为第一个humble数为1
        humbles[0] = 1;
        //依次求出humbles[i]
        for (int i = 1; i <= n; i++)
        {
            humbles[i] = Integer.MAX_VALUE;
            //考虑每一个素数
            for (int j = 0; j < k; j++)
            {
                //找到比上一个humble还大的乘积：a
                while (primes[j] * humbles[multiplyIndex[j]] <= humbles[i - 1])
                {
                    multiplyIndex[j]++;
                }
                //humble[i]为每一个素数所得a中的最小值
                humbles[i] = Math.min(humbles[i], primes[j] * humbles[multiplyIndex[j]]);
            }
        }

        answer = humbles[n];
    }

http://blog.csdn.net/linraise/article/details/12587585

1. int pIndex[101],Ugly[100005];  
2. void Ugly_Num(int* Prime,int K,int N)  
3. {  
4.     int i,j,min,minIndex;  
5.     for(i=0;i<K;++i)  
6.         pIndex[i]=0;//初始化为0，因为初始状态第i个状态已经乘到0位,0位的值是1  
7.     Ugly[0]=1;  
8.     for(i=1;i<=N;)//找出从1到N的丑数，太暴力了,提示：注意第3位置留空！！！  
9.     {  
10.         min=INT_MAX;  
11.         for(j=0;j<K;++j)//找到最小值，K个素数分别和之前的丑数相乘求出最小的那一个  
12.         {  
13.             //(j,pIndex[j])表示第j个素数已经乘到了第pIndex[j]位了，比如说8=2*4,2是第0个素数，4是第3位，则pIndex[0]=3  
14.             //下一次，prime[j]乘pIndex[j]+1位就可以了，因为再乘之前的也只会比这小  
15.             if(Prime[j]*Ugly[pIndex[j]] < min)  
16.             {  
17.                 min=Prime[j]*Ugly[pIndex[j]];  
18.                 minIndex=j;//最小的素数索引  
19.             }  
20.         }  
21.         if( min != Ugly[i-1]) //如果和之前的不一样，更新之,否则只更新相乘的位，因为下一次对应的素数要乘更大的丑数  
22.             Ugly[i++]=min;  
23.         ++pIndex[minIndex];//素数索引  
24.     }  
25.     cout<<Ugly[N]<<endl;  
26. } 

http://www.cnblogs.com/hoskey/p/3803083.html

13 int main()
14 {
15     ll k,n,i,j,l,minp=0;
16     //文件操作
17     freopen("humble.in","r",stdin);
18     freopen("humble.out","w",stdout);
19     memset(low,0,sizeof(low));
20     scanf("%lld%lld",&k,&n);
21     for (i=1;i<=k;i++) scanf("%lld",&S[i]);
22     sort(S+1,S+1+k);//排序 
23     N[0]=1;//初始化 
24     for (i=1;i<=n;i++)//求第I个丑数 
25     {
26         ll temp=0x7fffffff;
27         for (j=1;j<=k;j++)
28         {
29             while (S[j]*N[low[j]]<=N[i-1]) low[j]++;
30             if (S[j]*N[low[j]]<temp)
31             {
32                 temp=S[j]*N[low[j]];
33                 minp=j;
34             }
35         }
36         N[i]=temp;
37         low[minp]++;
38     }
39     printf("%lld",N[n]);
40     return 0;
41 }

Read full article from humblenumbers - codetrick