UVA 136 - Ugly Numbers

UVA 136 - Ugly Numbers

題目概述:

輸出第1500個醜數。

醜數定義為質因數只有2或3或5的數。

思路:

不斷的找下一個醜數。

利用一個priority_queue，找出最小的數，接著再丟入該數*2跟*3跟*5的數，但要避免重複丟入，所以就利用一個map來對照是否丟入過。

AC code:

//By SCJ

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

#define int long long

map<int,bool> mp;

main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   int cnt=0,ans;

   priority_queue<int,vector<int>,greater<int>> pq;

   pq.push(1);mp[1]=1;

   while(1)

   {

       int tp=pq.top();pq.pop();cnt++;

       if(cnt==1500){ans=tp;break;}

       if(mp[tp*2]==0) pq.push(tp*2),mp[tp*2]=1;

       if(mp[tp*3]==0) pq.push(tp*3),mp[tp*3]=1;

       if(mp[tp*5]==0) pq.push(tp*5),mp[tp*5]=1;

   }

   cout<<"The 1500'th ugly number is "<<ans<<"."<<endl;

}