Humble Numbers（搜索，生成子集）
题目：
给出多次询问，问第k个丑数是多少(最多询问到k = 5842)。
丑数：分解质因数后，质因子只包含2,3,5,7的数字。
思路：
通过预处理得到，5842个丑数就行。这里可以使用dfs来进行预处理。
实现：
注意一下这个毒瘤的输出，对于11、12、13结尾是th。其他是根据末尾数字决定的。
map<int, int> vis;
int a[] = {2, 3, 5, 7};
int s[6005], idx = 0;
void dfs(int cur, int l)
{
for(int i = l; i < 4; l ++)
{
if(cur * 1ll * a[i] > 2e9) continue;
if(vis.find(cur * a[i]) == vis.end())
{
vis[cur * a[i]] = 1;
s[++ idx] = cur * a[i];
dfs(cur * a[i], i);
}
}
}
int main()
{
vis[1] = 1;
s[++ idx] = 1;
dfs(1, 0);
sort(s + 1, s + idx + 1);
int x;
while(~scanf("%d", &x))
{
if(!x) break;
if(x % 10 == 1 && (x % 100) != 11)
printf("The %dst humble number is %d.\n", x, s[x]);
else if(x % 10 == 2 && (x % 100) != 12)
printf("The %dnd humble number is %d.\n", x, s[x]);
else if(x % 10 == 3 && (x % 100) != 13)
printf("The %drd humble number is %d.\n", x, s[x]);
else
printf("The %dth humble number is %d.\n", x, s[x]);
}
}