UVA 136 - Ugly Numbers（优先队列 + 集合）

题目大意：

所谓丑数，就是除了2 3 5 ，都不能被其他素数整除，输出第1500个丑数。

解题思路：

派生的思想，x是丑数，那么2x 3x 5x都是丑数，每次取最小的数，然后通过这个数派生，然后存入集合，直到取到第1500小的时候输出队首元素即可。AC代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
using namespace std;
typedef long long ll;
int main()
{
    priority_queue<ll, vector<ll >, greater<ll > > q;
    set<ll > s;
    ll a[5] = {2, 3, 5};
    int k = 0;
    q.push(1);
    s.insert(1);
    while (++k)
    {
        ll n = q.top();//每次取队首元素，利用队首元素派生
        q.pop();
        if (k == 1500)
        {
            printf("The 1500'th ugly number is %lld.\n", n);
            break;
        }
        for (int i = 0; i < 3; i ++)
        {
            ll t = n * a[i];
            if (!s.count(t))//如果这个数是第一次出现则入队
            {
                s.insert(t);
                q.push(t);
            }
        }
    }
    return 0;
}