题解 P2723 【丑数 Humble Numbers】
我们在数组 hum 中计算出前 n 个丑数。为了实现起来更简单，我们把 1 也作为一个丑数，算法也要因此略微调整一下。
当我们已知前 k 个丑数，想得到第 k+1 个，我们可以这样做：对于每个质数 p，寻找最小的丑数 h，使得 hp上一个丑数大。取我们找到的 hp中最小的一个，它就是下一个丑数。
为了使搜索更快，我们可以为每个质数维护一个引“pindex”表示每个质数已经乘到了哪个丑数，每次都从那里开始，而不是再从头再来。
方法二
这道题可以用 BFS+Treap 来做。但这里的 BFS 不使用队列来扩展，而是用 Treap 来扩展。
建一个 Treap 保存已经得到的数，从小到大每次从堆中取出一个数，用它和集合中的质数相乘，查找判断它是否重复.如果没有重复，那么将它插入到 Treap 中。直到产生了 n 个数 ， 那么再往后扩展一位，得到的第 n 个数既为所求的结果。时间复杂度：BFS 扩展为 O(N)，
查第 k 大为 O(logN)判重为 O(logN)，插入为 O(logN)，因此总的复杂度为 O(NlogN)
我的思路是每次从堆中取一个，然后从质数集合里扫一遍。虽然不能保证新扩展出的数的顺序，但很类似 Astar，第 n 个开始扩展的节点可以确定，复杂度应该为 nklogn，可惜内存不够
方法三
这道题目可以直接应用 STL 中的 priority_queue 来做，复杂度为 O(NKlogN)，对于第 i小的数，扩充它能得到的所有新元素并插入 priority_queue 中，然后 pop 第ｉ小的数。
时间没问题，但是空间会爆，当然只对于最后一个数据，我最后一个数据在自己机子上 RUN 完后，骗过去的，USACO 上分配内存太小!