C++の超醜い数

n番目の非常に醜い数を見つけるには、1つの関数を作成する必要があります。超醜い数は正の数であり、そのすべての素因数はサイズkの与えられた素数リストの素数にあります。したがって、nが12で、素数が[2、7、13、19]の場合、出力は32になります。これは、[1、2、4、7、8、13、14、16、19、26、 28、32]は12個の非常に醜い数のシーケンスです。

これを解決するには、次の手順に従います-

• num、prime、idxを使用してデータ構造トリプレットを作成します

• nが1の場合、1を返し、サイズn + 1の配列を作成し、これに1を入力します

• 優先キューpqを定義する

• 0から素数のサイズまでの範囲のiの場合-

  • トリプレットを作成するt（primes [i]、primes [i]、2）

• 2からnの範囲のiの場合

  • curr：=pqの最上位要素、次にpqから削除

  • val：=currの数

  • v [i]：=val

  • currの数：=currの素数*v[currのインデックス]

  • currのインデックスを1増やします

  • currをpqに挿入します

  • 一方、val =pq topの数、

    • curr：=pqの先頭で、pqから削除

    • currの数：=currの素数*v[currのインデックス]

    • currのインデックスを1増やします

    • currをpqに挿入します

• v [n]

  を返す

例（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 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));
}

入力

12
[2,7,13,19]

出力

32