POJ 1338 Ugly Numbers

問題

http://poj.org/problem?id=1338
2,3,5のみが素因数の数をUgly number という。便宜上１もUgly number とする。n番目のUgly number を求めよ。n <= 1500

やりかた

プライオリティキューに生成した数を入れていきながら幅優先探索。要long long。
setに発見した数を入れながら同じ数字の探索を避ける。
以下ソース。

ll num[2000];

int main(){
  int k = 0;
  priority_queue<ll, vector<ll>, greater<ll> > q;
  set<ll> visit;
  q.push(1);
  while(!q.empty() && k < 1600){
    ll a = q.top(); q.pop();
    if(!visit.insert(a).second) continue;
    num[k++] = a;
    q.push(a * 2), q.push(a * 3), q.push(a * 5);
  }
  sort(num, num + k);
  int n;
  while(cin >> n, n) cout << num[n - 1] << endl;
}