hud_1058   Humble Numbers

hud_1058   Humble Numbers

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1058 

题目原文： 

 题意：

该题就是让我们找出题意里所谓的“Humble Numbers”，根据题目的意思，‘Humble Numbers’指的是一个数的所有质因子必须由2，3，5和7组成，非质因子无要求，例如14，它的因子为1，2，7，14，它的质因子为7，而7是在{2，3，5，7}这个集合里的，所以14是Humble Numbers，例如22，它的因子为1，2，11，22，它的质因数有2，11，然而11不在{2，3，5，7}这个集合里面，所以22不是Humble Numbers。题目的要求就是让我们找出第i个Humble Numbers。

解题思路：

根据题目意思，Humble Numbers的质因数自能是{2，3，5，7}，所以Humble Numbers = ，根据这个推导式子打表即可得到最后的答案。（这里注意如果一个数没有质因子，那么它也是Humble Numbers）。

题目的注意点：

该题目需要注意的第一个注意点在解题思路上已经提及，第二个主意点的是它的输出格式，其中末尾由11，12，13这三个数组成的，就用-th，如果除末尾11，12，13之外，末尾由1组成，则用-st，末尾由2组成，则用-nd，末尾由3组成，则用-rd，除此之外，全部使用-th。

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 6000;
int num[maxn];  //用于存取Humble number序列
int main()
{num[0] = 0, num[1] = 1;int l1,l2,l3,l4;l1 = l2 = l3 = l4 =1;for(int i = 2; i < maxn; i++){num[i] = min(min(num[l1]*2, num[l2]*3), min(num[l3]*5, num[l4]*7));if(num[i] == 2*num[l1]) l1++;if(num[i] == 3*num[l2]) l2++;if(num[i] == 5*num[l3]) l3++;if(num[i] == 7*num[l4]) l4++;}                                    //使用推导式打表得出Humble number数序列int n;while(cin>>n){if(n == 0){break;      // 是0就结束程序，跳出循环 }if(n % 100 == 11 or n % 100 == 12 or n % 100 == 13){printf("The %dth humble number is %d.\n", n, num[n]);}else if(n % 10 ==1){printf("The %dst humble number is %d.\n", n, num[n]);}else if(n % 10 ==2){printf("The %dnd humble number is %d.\n", n, num[n]);}else if(n % 10 ==3){printf("The %drd humble number is %d.\n", n, num[n]);}else{printf("The %dth humble number is %d.\n", n, num[n]);}}return 0;
}