การลบขั้นต่ำจากอาร์เรย์เพื่อทำให้ GCD ยิ่งใหญ่ขึ้นใน C ++

แนวคิด

สำหรับตัวเลข N ที่กำหนด เป้าหมายคือการกำหนดการลบตัวเลขขั้นต่ำเพื่อให้ GCD ของตัวเลขที่เหลือมากกว่า GCD เริ่มต้นของตัวเลข N หากไม่สามารถเพิ่ม GCD ได้ ให้พิมพ์ “NO”

ป้อนข้อมูล

b[] = {1, 2, 4}

ผลผลิต

1

หลังจากลบองค์ประกอบแรกแล้ว GCD ใหม่จะเป็น 2 ซึ่งมากกว่า initialGCD นั่นคือ 1

ป้อนข้อมูล

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

ผลผลิต

3

gcd เริ่มต้นคือ 3 หลังจากลบ 6 และ 9 เพื่อให้ได้ gcd เท่ากับ 15 ซึ่งมากกว่า 3 เราสามารถลบ 9 และ 15 เพื่อให้ได้ gcd เท่ากับ 6

วิธีการ

เราควรทำตามขั้นตอนต่อไปนี้เพื่อแก้ปัญหาข้างต้น -

• อันดับแรก เราควรกำหนด gcd ของตัวเลข N โดยใช้อัลกอริทึมแบบยุคลิด

• เราควรหารตัวเลขทั้งหมดด้วย gcd ที่กำหนด

• การใช้การแยกตัวประกอบเฉพาะสำหรับเทคนิคการสืบค้นหลายรายการ เราควรกำหนดการแยกตัวประกอบเฉพาะของทุกตัวเลขใน O(log N)

• เราต้องแทรกตัวประกอบเฉพาะในชุดเพื่อกำจัดรายการซ้ำที่ได้รับโดยใช้วิธีนี้

• การใช้วิธีการแฮชแมป เราควรนับความถี่ของปัจจัยเฉพาะในทุกองค์ประกอบที่ i

• ในช่วงเวลาที่มีการแยกตัวประกอบของตัวเลข และจำนวนนับถูกเก็บไว้ในตารางความถี่ ให้วนซ้ำใน hash-map และกำหนดปัจจัยเฉพาะซึ่งเกิดขึ้นเป็นจำนวนมากที่สุด ปัจจัยเฉพาะนี้ไม่สามารถเป็น N ได้ เนื่องจากเราได้แบ่งองค์ประกอบอาร์เรย์ในขั้นต้นด้วย gcd เริ่มต้นของตัวเลข N

• ด้วยเหตุนี้ จำนวนการลบจะเป็น N-(hash[prime_factor]) เสมอ หากมีปัจจัยดังกล่าวหลังจากการแบ่ง gcd เริ่มต้น

ตัวอย่าง

// 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