Khái niệm
Đối với N số đã cho, mục tiêu là xác định loại bỏ tối thiểu các số sao cho GCD của các số còn lại lớn hơn GCD ban đầu của N số. Nếu không thể tăng GCD, hãy in “KHÔNG”.
Đầu vào
b[] = {1, 2, 4} Đầu ra
1
Sau khi xóa phần tử đầu tiên, GCD mới là 2, lớn hơn GCD ban đầu, tức là 1.
Đầu vào
b[] = {6, 9, 15, 30} Đầu ra
3
Gcd ban đầu là 3, sau khi loại bỏ 6 và 9 để có gcd là 15 lớn hơn 3. Chúng ta cũng có thể xóa 9 và 15 để có gcd là 6.
Phương pháp
Chúng ta nên làm theo các bước sau để giải quyết vấn đề trên -
-
Lúc đầu, chúng ta nên xác định gcd của N số áp dụng thuật toán Euclide.
-
Chúng ta nên chia tất cả các số cho gcd đã xác định.
-
Áp dụng kỹ thuật phân tích thừa số nguyên tố cho nhiều truy vấn, chúng ta nên xác định thừa số nguyên tố của mọi số trong O (log N).
-
Chúng tôi phải chèn tất cả các thừa số nguyên tố trong tập hợp để loại bỏ các phần tử trùng lặp thu được khi áp dụng phương pháp này.
-
Áp dụng phương pháp bản đồ băm, chúng ta nên đếm tần số của các thừa số nguyên tố trong mọi phần tử thứ i.
-
Tại thời điểm khi quá trình phân tích nhân tử của các số đã được thực hiện và số đếm đã được lưu trữ trong bảng tần số, hãy lặp lại trong bản đồ băm và xác định thừa số nguyên tố xuất hiện với số lần lớn nhất. Thừa số nguyên tố này không thể là N, vì ban đầu chúng ta đã chia các phần tử của mảng cho gcd ban đầu của N số.
-
Do đó, số lần xóa sẽ luôn là N- (hash [prime_factor]) nếu có bất kỳ yếu tố nào như vậy sau khi chia gcd ban đầu.
Ví dụ
// 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;
} Đầu ra
2