C++에서 GCD를 더 크게 만들기 위해 배열에서 최소 제거

<시간/>

컨셉

주어진 N개의 숫자와 관련하여 목표는 나머지 숫자의 GCD가 N개의 초기 GCD보다 크도록 숫자의 최소 제거를 결정하는 것입니다. GCD를 증가시킬 수 없는 경우 "NO"를 인쇄하십시오.

입력

b[] = {1, 2, 4}

출력

첫 번째 요소를 제거한 후 새 GCD는 2이며 initialGCD보다 큰 1입니다.

입력

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

출력

초기 gcd는 3이고, 6과 9를 제거하여 3보다 큰 15의 gcd를 얻습니다. 9와 15를 제거하여 6의 gcd를 얻을 수도 있습니다.

방법

위의 문제를 해결하려면 다음 단계를 따라야 합니다. -

먼저 유클리드 알고리즘을 적용하여 N개의 숫자의 gcd를 결정해야 합니다.
모든 숫자를 결정된 gcd로 나누어야 합니다.
다중 쿼리 기술에 대한 소인수 분해를 적용하여 O(log N)의 모든 숫자에 대한 소인수 분해를 결정해야 합니다.
이 방법을 적용하여 얻은 중복을 제거하려면 집합에 모든 소인수를 삽입해야 합니다.
해시맵 방식을 적용하여 모든 i번째 요소에서 소인수의 빈도를 계산해야 합니다.
숫자의 인수분해가 수행되고 빈도 테이블에 카운트가 저장되었을 때 해시 맵을 반복하여 가장 많이 발생하는 소인수를 결정합니다. 이 소인수는 N이 될 수 없습니다. 이미 배열 요소를 처음에 N 숫자의 초기 gcd로 나누었기 때문입니다.
따라서 초기 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;
}