数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中使数组 GCD 变大的最小移除次数
概念
对于给定的 N 个数字，目标是确定要移除的数字的最小数量，以便剩余数字的 GCD 大于 N 个数字的初始 GCD。如果无法增加 GCD，则打印“NO”。
输入
b[] = {1, 2, 4}输出
1
移除第一个元素后，新的 GCD 为 2，它大于初始 GCD，即 1。
输入
b[] = {6, 9, 15, 30}输出
3
初始 gcd 为 3，移除 6 和 9 后得到 gcd 为 15，它大于 3。我们也可以移除 9 和 15 以获得 gcd 为 6。
方法
我们应该遵循以下步骤来解决上述问题：
首先，我们应该应用欧几里得算法确定 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;
}输出
2
更新于: 2020-07-23
190 次浏览
广告