Số siêu xấu thứ n trong C++

Số siêu xấu (super ugly number): số dương mà mọi ước nguyên tố đều nằm trong danh sách primes cho trước. Tìm số siêu xấu thứ n.

Ví dụ: n=12, primes=[2,7,13,19] → Kết quả: 32. Dãy: [1,2,4,7,8,13,14,16,19,26,28,32].

Giải thuật (Min-Heap + Con trỏ)

1. Cấu trúc Data{num, prime, idx}: giá trị hiện tại, nguyên tố, chỉ số trong mảng kết quả.
2. Min-heap pq theo num.
3. Khởi tạo: v[1]=1, push (p, p, 2) cho mỗi p trong primes.
4. Với i=2..n:
5. Lấy curr nhỏ nhất từ pq, val = curr.num, v[i]=val.
6. Cập nhật curr.num = curr.prime * v[curr.idx], curr.idx++, push lại.
7. Loại bỏ trùng lặp: while pq.top().num == val, pop, cập nhật tương tự, push lại.
8. Trả về v[n].

Ví dụ C++

#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 p : primes) pq.push(Data(p, p, 2));
        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];
    }
};

int main() {
    Solution ob;
    vector<int> v = {2,7,13,19};
    cout << ob.nthSuperUglyNumber(12, v);
    return 0;
}

Đầu vào

12 [2,7,13,19]

Đầu ra

32