题目大意：

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, … 
shows the first 10 ugly numbers. By convention, 1 is included. 
把只含有2.3.5因数的数称为丑数，默认第一个丑数是1。 
POJ是有多次询问，输出第n个丑数 
UVA是询问第1500个丑数是多少。

思路：

利用STL的优先队列，创建一个小数优先的优先队列，然后每次取队头，分别乘以2.3.5，利用map看是否被放入过队列。从而得到按照大小顺序排列的丑数。

代码：

UVA

 1 #include
 2 using namespace std;
 3 typedef long long ll;
 4 int main()
 5 {
 6     ll num=1;
 7     priority_queue,greater > q;//小数优先的优先队列
 8     map mp;
 9     int x[3]={2,3,5},cnt=1;
10     q.push(num);
11     mp[num]++;
12     while(!q.empty())
13     {
14         num=q.top();
15         q.pop();
16         if(cnt==1500){
17             cout<<"The 1500‘th ugly number is "<"."<<endl;
18             break;
19         }
20         for(int i=0;i<3;++i){
21             ll a=num*x[i];
22             if(mp[a]==0){//对取过的丑数进行标记
23                 q.push(a);
24                 mp[a]++;
25             }
26         }
27         cnt++;
28     }
29     return 0;
30 }

View Code

POJ

 1  #include
 2 #include
 3 #include
 4 #include

View Code

UVA 136 & POJ1338 Ugly Numbers