题目连接

   

Super Ugly Number

Description

Write a program to find the $n^{th}$ super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.

Note:

(1) 1 is a super ugly number for any given primes.

(2) The given numbers in primes are in ascending order.

(3) $0 < k \leq 100, 0 < n \leq 10^6, 0 < primes[i] < 1000.$

优先队列。。

 

class Solution {private:    typedef long long ll;    struct Node {        ll val;        int idx, prim;        Node(ll _v_ = 0, int _i_ = 0, int _p_ = 0) :val(_v_), idx(_i_), prim(_p_) {}        inline bool operator<(const Node &x) const {            return val > x.val;        }    };    typedef priority_queue
     
       PQ;public:    int nthSuperUglyNumber(int n, vector
      
       & primes) {        PQ q;        vector
       
         ans(n + 10); ans[0] = 1;        int len = primes.size();        for (int i = 0; i < len; i++) {            q.push(Node(primes[i], 0, primes[i]));        }        for (int i = 1; i < n; i++) {            Node ret = q.top();            ans[i] = ret.val;            while (true) {                ret = q.top(); q.pop();                ret.val = ans[++ret.idx] * ret.prim;                q.push(ret);                if (q.top().val != ans[i]) break;            };        }        return (int)ans[n - 1];    }};