Số siêu xấu trong C ++

Chúng ta phải tạo một hàm để tìm số siêu xấu thứ n. Các số siêu xấu là các số dương mà tất cả các thừa số nguyên tố đều nằm trong danh sách các số nguyên tố đã cho có kích thước là k. Vì vậy, nếu n là 12 và số nguyên tố là [2, 7, 13, 19], thì kết quả sẽ là 32, điều này là do [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] là dãy 12 con số siêu xấu xí.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Tạo bộ ba cấu trúc dữ liệu, với num, số nguyên tố và idx
nếu n là 1, thì trả về 1, tạo một mảng có kích thước n + 1 và điền vào giá trị này bằng 1
xác định hàng đợi ưu tiên pq
cho tôi trong phạm vi 0 đến kích thước của số nguyên tố−
- tạo bộ ba t (số nguyên tố [i], số nguyên tố [i], 2)
cho tôi trong phạm vi từ 2 đến n
- curr:=phần tử trên cùng của pq, sau đó xóa khỏi pq
- val:=num of curr
- v [i]:=val
- num of curr:=prime of curr * v [index of curr]
- tăng chỉ số curr lên 1
- chèn curr vào pq
- while val =num of pq top,
  - curr:=top of pq và xóa khỏi pq
  - num of curr:=prime of curr * v [index of curr]
  - tăng chỉ số curr lên 1
  - chèn curr vào pq
trả về v [n]

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
struct Data{
   int num, prime, idx;
   Data(int a, int b, int c){
      num = a;
      prime = b;
      idx = c;
   }
};
struct Comparator{
   bool operator()(Data a, Data b){
      return !(a.num < b.num);
   }
};
class Solution {
   public:
   int nthSuperUglyNumber(int n, vector<int>& primes) {
      if(n == 1)return 1;
      vector <int> v(n + 1, 1);
      priority_queue < Data, vector < Data >, Comparator > pq;
      for(int i = 0; i < primes.size(); i++){
         pq.push(Data(primes[i], primes[i], 2));
      }
      int x;
      for(int i = 2; i <= n; i++){
         Data curr = pq.top();
         pq.pop();
         int val = curr.num;
         v[i] = val;
         curr.num = curr.prime * v[curr.idx];
         curr.idx++;
         pq.push(curr);
         while(val == pq.top().num){
            curr = pq.top();
            pq.pop();
            curr.num = curr.prime * v[curr.idx];
            curr.idx++;
            pq.push(curr);
         }
      }
      return v[n];
   }
};
main(){
   Solution ob;
   vector<int> v = {2,7,13,19};
   cout << (ob.nthSuperUglyNumber(12, v));
}

Đầu vào

12
[2,7,13,19]

Số siêu xấu trong C ++

Ví dụ (C ++)

Đầu vào

Đầu ra