Problem.png
书中介绍的一种典型的方法是从小到大生成丑数，思想类似于BFS。本题用到了一些数学技巧：最小的丑数是1，而对于任意丑数x，2x、3x和5x也都是丑数。这样，就可以用一个优先队列保存所有已生成的丑数，每次取出最小的丑数，生成3个新的丑数。需要注意的是，同一个丑数有多种生成方式，所以需要判断一个丑数是否已经生成过(使用set)，而且要考虑溢出问题(使用long long类型)。
#include <iostream>
#include <queue>
#include <vector>
#include <set>
using namespace std;
typedef long long LL;
int main() {
priority_queue<LL, vector<LL>, greater<LL> > q;
set<LL> s;
int coeff[3] = {2, 3, 5};
q.push(1);
s.insert(1);
LL x;
for (int i = 1; ; i++) {
x = q.top();
q.pop();
if (i == 1500) break;
for (int j = 0; j < 3; j++) {
if (!s.count(x * coeff[j])) {
q.push(x * coeff[j]);
s.insert(x * coeff[j]);
}
}
}
cout << "The 1500'th ugly number is " << x << "." << endl;
}
