最少从数组中删除内容以使GCD在C ++中更强大

概念

对于给定的N个数字，目标是确定数字的最小去除量，以使其余数字的GCD大于N个数字的初始GCD。如果无法增加GCD，请打印“否”。

输入值

b[] = {1, 2, 4}

输出结果

删除第一个元素后，新的GCD为2，大于初始GCD即1。

输入值

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

输出结果

移除6和9以获得大于15的gcd之后，初始gcd为3。我们还可以移除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
//这样剩余的gcd的计算得出的gcd将更大
//比N个数字的初始gcd-
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
//存储每个数字的最小素数
int spf1[MAXN];
//计算每个的SPF（最小素数）
//直到MAXN的数字。
//时间复杂度：O(nloglogn)
void sieve1(){
   spf1[1] = 1;
   for (int i = 2; i < MAXN; i++)
      //标记每个元素的最小素数
      //数字本身。
   spf1[i] = i;
   //每个偶数分别标记spf-
   //数字为2-
   for (int i = 4; i < MAXN; i += 2)
      spf1[i] = 2;
   for (int i = 3; i * i < MAXN; i++) {
      //检查我是否素数
      if (spf1[i] == i) {
         //将所有可被i整除的数字标记为SPF-
         for (int j = i * i; j < MAXN; j += i)
            //如果不是，则标记spf1 [j]
            //先前标记
            if (spf1[j] == j)
               spf1[j] = i;
      }
   }
}
//现在一个O（log n）函数返回质数分解
//通过在每一步除以最小素数
vector<int> getFactorization1(int x){
   vector<int> ret;
   while (x != 1) {
      ret.push_back(spf1[x]);
      x = x / spf1[x];
   }
   return ret;
}
//所以函数返回最小值
//清除所需的gcd-
//比以前更大
int minimumRemovals1(int a1[], int n){
   int g = 0;
   //查找初始gcd-
   for (int i = 0; i < n; i++)
      g = __gcd(a1[i], g);
   unordered_map<int, int> mpp;
   //将所有数字除以初始gcd-
   for (int i = 0; i < n; i++)
      a1[i] = a1[i] / g;
   //遍历所有数字
   for (int i = 0; i < n; i++) {
      //素数分解以获得素数
      //数组中第i个元素的因子
      vector<int> p = getFactorization1(a1[i]);
      set<int> s1;
      //将所有主要因素插入
      //设置删除重复项
      for (int j = 0; j < p.size(); j++) {
         s1.insert(p[j]);
      }
      ///增加素数
      //映射中每个元素的系数
      for (auto it = s1.begin(); it != s1.end(); it++) {
         int el = *it;
         mpp[el] += 1;
      }
   }
   int mini = INT_MAX;
   int mini1 = INT_MAX;
   //在映射中迭代并检查每个因素
   //及其数量
   for (auto it = mpp.begin(); it != mpp.end(); it++) {
      int fir1 = it->first;
      int sec1 = it->second;
      //检查最大的出现因素
      //没有出现在任何一个或多个中
      if ((n - sec1) <= mini) {
         mini = n - sec1;
      }
   }
   if (mini != INT_MAX)
      return mini;
   else
      return -1;
}
//驱动程式码
int main(){
   int a1[] = { 6, 9, 15, 30 };
   int n = sizeof(a1) / sizeof(a1[0]);
   sieve1();
   cout << minimumRemovals1(a1, n);
   return 0;
}

输出结果

基础教程