raghuvanshraj

313.cpp

Jul 30th, 2021
629
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  *    author:   vulkan
  3.  *    created:  29.07.2021 04:22:14 PM
  4. **/
  5. #include <bits/stdc++.h>
  6.  
  7. typedef long long LL;
  8.  
  9. using namespace std;
  10.  
  11. int nthSuperUglyNumber(int n, vector<int> &primes) {
  12.     priority_queue<LL, vector<LL>, greater<LL>> min_heap;
  13.     map<LL, bool> vis;
  14.     min_heap.push(1);
  15.     while (n--) {
  16.         LL x = min_heap.top();
  17.         min_heap.pop();
  18.         if (n == 0) {
  19.             return x;
  20.         }
  21.  
  22.         for (LL y : primes) {
  23.             if (not vis[x * y]) {
  24.                 min_heap.push(x * y);
  25.                 vis[x * y] = true;
  26.             }
  27.         }
  28.     }
  29.     return 0;
  30. }
  31.  
  32. int main(int argc, char const *argv[]) {
  33.     int n;
  34.     cin >> n;
  35.     int m;
  36.     cin >> m;
  37.     vector<int> primes(m);
  38.     for (int i = 0; i <= m - 1; ++i) {
  39.         cin >> primes[i];
  40.     }
  41.  
  42.     cout << nthSuperUglyNumber(n, primes);
  43.  
  44.     return 0;
  45. }
RAW Paste Data