1 /*
2 hdu1058 Humble Numbers DP
3 ymc 2008/9/23
4 题目大意：
5 如果一个数的没有2，3，5，7以外的质因子，则这个数
6 称为Humble数。前几个Humble数为
7 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18,
8 20, 21, 24, 25, 27, ...
9 求第n个Humble数。
10 分析与解题思路：
11 Humble数没有2，3，5，7以外的质因子，则
12 令h[]记录已经求到的Humble数，假设已经求了num个。
13 则把所有h[]中的数乘以2，3，5，7得到的最小大于h[num]的
14 数就是下一个Humble数。但这样无疑会TLE。
15 Prim[4]={2,3,5,7}
16 初始id[4]={1,1,1,1}
17 其中id[k]为h[]中的下标。表示乘以2的Humble数在h[]中的下标。
18 已经知道num个Humble数时，min{Prim[k]*H[id[k]},0<=k<=3，
19 就是要找的下一个Humble数。
20 注意重复的情况。
21 */
22 #include <iostream>
23 #include <limits>
24 using namespace std;
25 const int N=5843;
26 int num;
27 double Prim[4]={2,3,5,7};
28 int id[4]={1,1,1,1};//初始下标
29 int h[N];
30 char s[4][3]={"th","st","nd","rd"};
31 int Humble()//求下一个Humble数，
32 {
33 double Max=INT_MAX;//double类型，乘积可能会超出int。
34 double tmp;
35 int k;
36 for(int i=0;i<4;i++)
37 {
38 tmp=Prim[i]*h[id[i]];
39 if(tmp<Max)
40 {
41 Max=tmp;
42 k=i;
43 }
44 }
45 id[k]++;
46 return int(Max);
47 }
48 void Init()
49 {
50 h[1]=1;
51 num=1;
52 for(num=2;num<N;num++)
53 {
54 h[num]=Humble();
55 if(h[num]==h[num-1])//重复，重新再求。
56 num--;
57 }
58 }
59 void OutPut(int n)//输出，11，12，13特殊，其它1，2，3结尾的普通。
60 {
61 int k=0;
62 if(n%10==1&&n%100!=11)
63 k=1;
64 else if(n%10==2&&n%100!=12)
65 k=2;
66 else if(n%10==3&&n%100!=13)
67 k=3;
68 printf("The %d%s humble number is %d.\n",n,s[k],h[n]);
69 }
70 int main()
71 {
72 int n;
73 Init();
74 while(scanf("%d",&n),n)
75 {
76 OutPut(n);
77 }
78 }