C++-এ অ্যারে থেকে ন্যূনতম এলিমেন্ট রিমুভ করে GCD বড়ান

কনসেপ্ট

Nটি সংখ্যা দেওয়া আছে। ন্যূনতম কতগুলো সংখ্যা রিমুভ করলে বাকি সংখ্যাগুলোর GCD প্রাথমিক GCD-এর চেয়ে বড় হবে। অসম্ভব হলে "NO" প্রিন্ট করুন।

ইনপুট

b[] = {1, 2, 4}

আউটপুট

প্রথম এলিমেন্ট রিমুভ করলে নতুন GCD ২, যা প্রাথমিক GCD ১-এর চেয়ে বড়।

ইনপুট

b[] = {6, 9, 15, 30}

আউটপুট

প্রাথমিক GCD ৩, ৬ এবং ৯ রিমুভ করলে GCD ১৫ যা ৩-এর চেয়ে বড়। অথবা ৯ এবং ১৫ রিমুভ করলে GCD ৬।

পদ্ধতি

প্রথমে ইউক্লিডিয়ান অ্যালগরিদম দিয়ে N সংখ্যার GCD বের করুন।
সব সংখ্যাকে ঐ GCD দিয়ে ভাগ করুন।
প্রাইম ফ্যাক্টরাইজেশন ফর মাল্টিপল কুয়েরি টেকনিক দিয়ে প্রতিটি সংখ্যার প্রাইম ফ্যাক্টরাইজেশন O(log N)-এ করুন।
সব প্রাইম ফ্যাক্টর সেটে রাখুন ডুপ্লিকেট এড়াতে।
হ্যাশ ম্যাপ দিয়ে প্রতিটি প্রাইম ফ্যাক্টরের ফ্রিকোয়েন্সি কাউন্ট করুন।
ফ্যাক্টরাইজেশন শেষে হ্যাশ ম্যাপ থেকে সবচেয়ে বেশি ফ্রিকোয়েন্সি வালা প্রাইম ফ্যাক্টর বের করুন। এটি N হতে পারবে না কারণ প্রাথমিক GCD দিয়ে ভাগ করা হয়েছে।
রিমুভাল সংখ্যা = N - hash[prime_factor]।

উদাহরণ

#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 = 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] = a1[i] / g; 
    for (int i = 0; i < n; 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; 
    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; 
}