資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告