C++でGCDを大きくするためのアレイからの最小限の削除

コンセプト

与えられたN個の数に関して、目標は、残りの数のGCDがN個の数の初期GCDよりも大きくなるように数の最小除去を決定することです。 GCDを増やすことができない場合は、「NO」と印刷してください。

入力

b[] = {1, 2, 4}

出力

1

最初の要素を削除すると、新しいGCDは2になります。これは、最初のGCD、つまり1よりも大きくなります。

入力

b[] = {6, 9, 15, 30}

出力

3

6と9を削除して3より大きい15のgcdを取得した後、最初のgcdは3です。9と15を削除して6のgcdを取得することもできます。

メソッド

上記の問題を解決するには、次の手順に従う必要があります-

• 最初に、ユークリッドの互除法を適用してN個の数のgcdを決定する必要があります。

• すべての数値を決定されたgcdで割る必要があります。

• 複数のクエリ手法に素因数分解を適用するには、O（log N）のすべての数値の素因数分解を決定する必要があります。

• この方法を適用して得られる重複を排除するために、セットにすべての素因数を挿入する必要があります。

• ハッシュマップ法を適用して、i番目の要素ごとに素因数の頻度を数える必要があります。

• 数値の因数分解が実行され、度数分布表にカウントが格納された時点で、ハッシュマップを繰り返し、最も多く発生する素因数を決定します。配列要素を最初にN個の数の最初のgcdですでに分割しているため、この素因数をNにすることはできません。

• 結果として、最初のgcdの除算後にそのような要因がある場合、削除の数は常にN-（hash [prime_factor]）になります。

例

// This C++ program finds the minimum removals
// so that the calculated gcd of remaining numbers will be more
// than the initial gcd of N numbers
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
// storing smallest prime factor for every number
int spf1[MAXN];
// Calculates SPF (Smallest Prime Factor) for every
// number till MAXN.
// Time Complexity : O(nloglogn)
void sieve1(){
   spf1[1] = 1;
   for (int i = 2; i < MAXN; i++)
      // marks smallest prime factor for every
      // number to be itself.
   spf1[i] = i;
   // separately marks spf for every even
   // number as 2
   for (int i = 4; i < MAXN; i += 2)
      spf1[i] = 2;
   for (int i = 3; i * i < MAXN; i++) {
      // checks if i is prime
      if (spf1[i] == i) {
         // marks SPF for all numbers divisible by i
         for (int j = i * i; j < MAXN; j += i)
            // marks spf1[j] if it is not
            // previously marked
            if (spf1[j] == j)
               spf1[j] = i;
      }
   }
}
// Now a O(log n) function returning primefactorization
// by dividing by smallest prime factor at every step
vector<int> getFactorization1(int x){
   vector<int> ret;
   while (x != 1) {
      ret.push_back(spf1[x]);
      x = x / spf1[x];
   }
   return ret;
}
// So function which returns the minimal
// removals required to make gcd
// greater than previous
int minimumRemovals1(int a1[], int n){
   int g = 0;
   // finding initial gcd
   for (int i = 0; i < n; i++)
      g = __gcd(a1[i], g);
   unordered_map<int, int> mpp;
   // divides all number by initial gcd
   for (int i = 0; i < n; i++)
      a1[i] = a1[i] / g;
   // iterating for all numbers
   for (int i = 0; i < n; i++) {
      // primt factorisation to get the prime
      // factors of i-th element in the array
      vector<int> p = getFactorization1(a1[i]);
      set<int> s1;
      // insert all the prime factors in
      // set to remove duplicates
      for (int j = 0; j < p.size(); j++) {
         s1.insert(p[j]);
      }
      /// increase the count of prime
      // factor in map for every element
      for (auto it = s1.begin(); it != s1.end(); it++) {
         int el = *it;
         mpp[el] += 1;
      }
   }
   int mini = INT_MAX;
   int mini1 = INT_MAX;
   // iterate in map and check for every factor
   // and its count
   for (auto it = mpp.begin(); it != mpp.end(); it++) {
      int fir1 = it->first;
      int sec1 = it->second;
      // checking largest appearing factor
      // which does not appears in any one or more
      if ((n - sec1) <= mini) {
         mini = n - sec1;
      }
   }
   if (mini != INT_MAX)
      return mini;
   else
      return -1;
}
// Driver code
int main(){
   int a1[] = { 6, 9, 15, 30 };
   int n = sizeof(a1) / sizeof(a1[0]);
   sieve1();
   cout << minimumRemovals1(a1, n);
   return 0;
}

出力

2