[UVA] 136 - Ugly Numbers

題意:
醜數:質因數只有2 3 5，
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40...這些都是醜數
求第1500個醜數。

方法:
醜數一定是2a*3b*5c，其中 a,b,c >= 0，
所以先把2 3 5放進優先佇列，一個一個pop，
取出後分別將*2和*3和*5的數再push進去佇列，
pop第1500次就是答案囉
(答案:859963392)


/* 20150801
 * hanting
 * UVa 136 - Ugly Numbers
 * C++
 */
#include <iostream>
#include <map>
#include <queue>
using namespace std;

int main()
{
    long long init[]={5,3,2,1};
    priority_queue<long long,vector<long long>,greater<long long> > prq(init,init+4);
    map<long long,long long> Map;
    Map[1]=Map[2]=Map[3]=Map[5]=1;
    for(long long i=0;i<1500-1;i++)
    {
        long long x2,x3,x5;
        long long top=prq.top();
        prq.pop();
        x2=top*2;
        x3=top*3;
        x5=top*5;
        if(Map[x2]==0)
        {
            prq.push(x2);
            Map[x2]=1;
        }
        if(Map[x3]==0)
        {
            prq.push(x3);
            Map[x3]=1;
        }
        if(Map[x5]==0)
        {
            prq.push(x5);
            Map[x5]=1;
        }
    }
    cout<<"The 1500'th ugly number is "<<prq.top()<<"."<<endl;
    return 0;
}