การลบสมาชิกน้อยที่สุดจากอาร์เรย์เพื่อทำให้ GCD เพิ่มขึ้นใน C++

แนวคิด

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

ตัวอย่าง: - {1, 2, 4} → GCD เริ่มต้น=1, ลบ 1 → เหลือ {2,4} GCD=2 > 1 → ลบ 1 ตัว - {6, 9, 15, 30} → GCD เริ่มต้น=3, ลบ 6,9 → เหลือ {15,30} GCD=15 > 3 → ลบ 2 ตัว

วิธีการแก้ปัญหา

1. หา GCD เริ่มต้นของทั้ง N ตัว
2. หารทุกตัวด้วย GCD เริ่มต้น
3. Prime factorization ทุกตัว (ใช้ Sieve + SPF - Smallest Prime Factor)
4. นับความถี่ของแต่ละเฉพาะตัว (นับ unique ต่อตัวเลข)
5. หาเฉพาะตัวที่ปรากฏมากที่สุด → เก็บตัวเลขที่มีเฉพาะตัวนี้ไว้ ลบที่เหลือ
6. คำตอบ = N - max_frequency

ตัวอย่างโค้ด C++

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

void sieve1(){ ... } // Sieve สำหรับ SPF

vector<int> getFactorization1(int x){ ... } // Factorization ด้วย SPF

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++) mpp[*it] += 1;
    }
    int mini = INT_MAX;
    for (auto it = mpp.begin(); it != mpp.end(); it++) {
        if ((n - it->second) <= mini) mini = n - it->second;
    }
    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;
}

ผลลัพธ์

2