UVa 136, POJ 1338 - Ugly Numbers

uva-136-ugly-numbers.cpp

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

typedef long long lld;

struct node {
	node(lld d, int p) : data(d), prev(p) {}
	lld data;
	int prev;
	bool operator < (const node& p) const {
		return data > p.data;
	}
};

int main() {
	priority_queue<node> pq;
	pq.push(node(1, 0));
	int mul[] = { 2, 3, 5 };
	vector<lld> v;
	while (v.size() < 1500) {
		node c = pq.top();
		pq.pop();
		v.push_back(c.data);
		for (int i = c.prev; i < 3; ++i) {
			lld x = c.data * mul[i];
			pq.push(node(x, i));
		}
	}
	for (int n; ~scanf("%d", &n) && n;) {
		printf("%lld\n", v[n - 1]);
	}
	return 0;
}