思路
set(存不重复且单调的Ugly Numbers) ( + 单调队列)
Ugly Numbers * {2, 3, 5} -> Ugly Numbers
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
set<ll> s;
ll a[3] = {2, 3 ,5};
int main()
{
s.insert(1);
int cnt = 0;
for(;;)
{
for(int i = 0; i < 3; i ++ )
{
ll x = *s.begin();
s.insert(x * a[i]);
}
s.erase(s.begin());
cnt ++ ;
if(cnt == 1499)
{
cout << "The 1500'th ugly number is " << *s.begin() << "." << endl;
break;
}
}
return 0;
}