Số lần xóa ít nhất để GCD mảng tăng lên trong C++

Khái niệm

Cho N số, tìm số lượng phần tử cần xóa ít nhất sao cho GCD các số còn lại lớn hơn GCD ban đầu của N số. Nếu không thể → in "NO".

Ví dụ 1: {1,2,4} → xóa 1 phần tử (1), GCD mới = 2 > 1.

Ví dụ 2: {6,9,15,30} → GCD ban đầu = 3. Xóa 6,9 → GCD=15; hoặc xóa 9,15 → GCD=6. Kết quả: 2 (code gốc in 2 nhưng giải thích nói 3, cần kiểm tra lại).

Phương pháp

1. Tính GCD ban đầu g của toàn mảng.
2. Chia mọi phần tử cho g.
3. Phân tích thừa số nguyên tố mỗi phần tử (dùng sàng SPF - Smallest Prime Factor).
4. Đếm tần suất mỗi thừa số nguyên tố (loại bỏ trùng lặp trong cùng một phần tử).
5. Thừa số xuất hiện nhiều nhất (freq) cho biết ta giữ lại freq phần tử có thừa số đó. Số lần xóa = N - freq.

Ví dụ (C++)

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
int spf1[MAXN];

void sieve1(){
    spf1[1]=1;
    for(int i=2;i<MAXN;i++) spf1[i]=i;
    for(int i=4;i<MAXN;i+=2) spf1[i]=2;
    for(int i=3;i*i<MAXN;i++) if(spf1[i]==i)
        for(int j=i*i;j<MAXN;j+=i) if(spf1[j]==j) spf1[j]=i;
}

vector<int> getFactorization1(int x){
    vector<int> ret;
    while(x!=1){ ret.push_back(spf1[x]); x/=spf1[x]; }
    return ret;
}

int minimumRemovals1(int a1[], int n){
    int g=0;
    for(int i=0;i<n;i++) g=__gcd(a1[i],g);
    unordered_map<int,int> mpp;
    for(int i=0;i<n;i++) a1[i]/=g;
    for(int i=0;i<n;i++){
        vector<int> p=getFactorization1(a1[i]);
        set<int> s1(p.begin(), p.end());
        for(int el: s1) mpp[el]++;
    }
    int mini=INT_MAX;
    for(auto it: mpp) mini=min(mini, n-it.second);
    return (mini!=INT_MAX)?mini:-1;
}

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