最少从数组中删除内容以使GCD在C ++中更强大
概念
对于给定的N个数字，目标是确定数字的最小去除量，以使其余数字的GCD大于N个数字的初始GCD。如果无法增加GCD，请打印“否”。
输入值
b[] = {1, 2, 4}输出结果
1
删除第一个元素后，新的GCD为2，大于初始GCD即1。
输入值
b[] = {6, 9, 15, 30}输出结果
3
移除6和9以获得大于15的gcd之后，初始gcd为3。我们还可以移除9和15以获得6的gcd。
方法
我们应该按照以下步骤解决以上问题-
首先，我们应该使用欧几里得算法确定N个数的gcd。
我们应将所有数字除以确定的gcd。
将素数分解应用于多次查询技术，我们应该确定O（logN）中每个数字的素数分解。
我们必须在集合中插入所有素因，以消除使用此方法获得的重复项。
应用哈希映射方法，我们应该计算第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（logn）函数返回质数分解
//通过在每一步除以最小素数
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;
}输出结果
2