C++ 알고리즘: 배열에서 최소 개수의 원소를 제거해 GCD를 더 크게 만들기

문제 개념

주어진 N개의 숫자에 대해, 남은 숫자들의 GCD(최대공약수)가 처음 N개 숫자의 GCD보다 커지도록 만들기 위해 제거해야 하는 원소의 최소 개수를 구하는 것이 목표입니다. 만약 GCD를 증가시키는 것이 불가능하다면 "NO"를 출력합니다.

입력 예시 1

b[] = {1, 2, 4}

출력

첫 번째 원소인 1을 제거하면 새로운 GCD는 2가 되며, 이는 초기 GCD인 1보다 큽니다.

입력 예시 2

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

출력

초기 GCD는 3입니다. 6과 9를 제거하면 남은 {15, 30}의 GCD는 15가 되어 3보다 커집니다. 마찬가지로 9와 15를 제거하면 GCD가 6이 됩니다. 한 번의 제거로는 GCD를 증가시킬 수 없으므로, 최소 제거 횟수는 2입니다.

접근 방법

위 문제는 다음 단계를 따라 해결할 수 있습니다.

먼저 유클리드 호제법(Euclidean Algorithm)을 이용해 N개 숫자의 초기 GCD를 구합니다.
배열의 모든 숫자를 구한 GCD로 나눕니다. 이렇게 하면 남은 값들의 공통 인수는 더 이상 초기 GCD의 인수가 아닙니다.
여러 쿼리에 대응할 수 있는 소인수분해 기법(최소 소인수, SPF 활용)을 적용해 각 숫자를 O(log N) 시간에 소인수분해합니다.
얻은 소인수들을 집합(set)에 삽입하여 중복을 제거합니다.
해시맵(hash-map)을 이용해 각 소인수가 몇 개의 원소에서 등장하는지 빈도를 계산합니다.
소인수분해가 완료되고 빈도 테이블에 개수가 저장되면, 해시맵을 순회하며 가장 많이 등장하는 소인수를 찾습니다. 이 소인수의 빈도는 N일 수 없습니다. 배열 원소를 이미 초기 GCD로 나누었기 때문입니다.
결과적으로, 초기 GCD로 나눈 후 조건을 만족하는 소인수가 존재한다면 필요한 제거 횟수는 항상 N - hash[prime_factor]가 됩니다.

예제 코드

// 이 C++ 프로그램은 남은 숫자들의 GCD가
// 초기 N개 숫자의 GCD보다 커지도록 하는
// 최소 제거 횟수를 구합니다.
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
// 모든 숫자에 대한 최소 소인수(SPF)를 저장
int spf1[MAXN];
// MAXN까지의 모든 숫자에 대해 SPF를 계산합니다.
// 시간 복잡도 : O(nloglogn)
void sieve1(){
    spf1[1] = 1;
    for (int i = 2; i < MAXN; i++)
        // 모든 숫자의 최소 소인수를 자기 자신으로 표시
        spf1[i] = i;
    // 짝수는 별도로 2로 표시
    for (int i = 4; i < MAXN; i += 2)
        spf1[i] = 2;
    for (int i = 3; i * i < MAXN; i++) {
        // i가 소수인지 확인
        if (spf1[i] == i) {
            // i로 나누어 떨어지는 모든 숫자의 SPF 표시
            for (int j = i * i; j < MAXN; j += i)
                // 아직 표시되지 않은 경우에만 spf1[j] 설정
                if (spf1[j] == j)
                    spf1[j] = i;
        }
    }
}
// 매 단계마다 최소 소인수로 나누어
// O(log n) 시간에 소인수분해 결과를 반환하는 함수
vector<int> getFactorization1(int x){
    vector<int> ret;
    while (x != 1) {
        ret.push_back(spf1[x]);
        x = x / spf1[x];
    }
    return ret;
}
// GCD를 이전 값보다 크게 만들기 위해
// 필요한 최소 제거 횟수를 반환하는 함수
int minimumRemovals1(int a1[], int n){
    int g = 0;
    // 초기 GCD 계산
    for (int i = 0; i < n; i++)
        g = __gcd(a1[i], g);
    unordered_map<int, int> mpp;
    // 모든 숫자를 초기 GCD로 나눔
    for (int i = 0; i < n; i++)
        a1[i] = a1[i] / g;
    // 모든 숫자에 대해 반복
    for (int i = 0; i < n; i++) {
        // 소인수분해로 배열의 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;
}

출력

시간 복잡도 분석

SPF(최소 소인수) 전처리에는 O(MAXN log log MAXN)의 시간이 걸리며, 각 숫자의 소인수분해는 O(log N), 전체 알고리즘은 배열 순회를 포함해 약 O(N log N + MAXN log log MAXN) 안에 동작합니다. 이 방식은 소수 판정과 빈도 계산을 결합해 효율적으로 최소 제거 횟수를 도출합니다.