Humble Numbers 解题报告

最初想到一个很直接的方法，代码如下：

01 void solve()
02 {
03     long i;
04     long c;
05     for(i = 2,c = 0;i <= LONG_MAX;i ++)
06     {
07         if(check(i))
08             c ++;
09         if(c == N)
10         {
11             printf("%ld\n",i);
12             break;
13         }
14     }
15 }

check(int i)函数用于检查i是否可以由输入文件中的质数构成。
这个算法很悲催地超时了，仅仅过了三个点，因为题目中humble number的上限是LONG_MAX。

然后想到DP方法，用布尔数组表示某个数是否是Humble Number，如果是，那么它乘上一个质数也是Humble number，但是，由于空间只有16M，这个算法所需空间估计要几百M，DP被迫放弃。

最后忍不住看了题解，题解给的方法也很直白：直接按顺序构造Humble number.

Once we have the first k humble numbers and want to compute the k+1st, we do the following:

for each prime p
  find the minimum humble number h
  such that h * p is bigger than the last humble number.
     take the smallest h * p found: that's the next humble number.

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <limits.h>
04
05 void solve();
06
07 long prime[101];
08 long pos[101];    //用于加快计算下一个Humble number的速度，非常巧妙
09 long humble[100001];
10 long N,K;
11
12 void solve();
13
14 int main()
15 {
16     long i;
17     freopen("humble.in","r",stdin);
18     freopen("humble.out","w",stdout);
19     scanf("%ld%ld",&K,&N);
20     for(i = 0;i < K;i ++)
21         scanf("%ld",&prime[i]);
22     solve();
23     fclose(stdout);
24     fclose(stdin);
25     return 0;
26 }
27
28 void solve()
29 {
30     long i;
31     long min,minp;
32     long count = 0;
33     humble[count ++] = 1;   //把1看作第0个Humble number，便于下面的计算
34     for(i = 0;i < K;i ++)
35         pos[i] = 0;
36     while(count <= N)
37     {
38         min = LONG_MAX;
39         for(i = 0;i < K;i ++)
40         {
41             while(prime[i] * humble[pos[i]] <= humble[count - 1])
42                 pos[i] ++;
43             //神奇的pos数组
44             if(prime[i] * humble[pos[i]] < min)
45             {
46                 min = prime[i] * humble[pos[i]];
47                 minp = i;
48             }
49         }
50         humble[count ++] = min;
51         pos[minp] ++;  //这句不是必须的
52     }
53     printf("%ld\n",humble[N]);
54 }

真感叹pos数组的奇妙啊。pos[i]表示prime[i] * 某个humble数恰好大于前一个Humble数时这个humble数的位置。由于humble数组是递增的，因此可以大大节约时间，不需要每次都从第0个humble数开始搜索。