超级丑数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef long long LL;
class Solution {
 public:
  int nthSuperUglyNumber(int n, vector<int>& primes) {
    unordered_set<LL> s;
    priority_queue<LL, vector<LL>, greater<LL>> q;
    q.push(1l);
    s.insert(1l);
    while (n--) {
      auto t = q.top();
      q.pop();
      if (n == 0) return (int)t;
      for (auto x : primes) {
        if (!s.count(t * x)) {
          s.insert(t * x);
          q.push(t * x);
        }
      }
    }
    return -1;
  }
};