[BOJ 27470 // C++] 멋진 부분집합

 

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 27470번 문제인 멋진 부분집합이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/27470

 

주어진 원소 중 절반 이상의 원소가 특정 소인수를 포함하고 있다면, 임의의 원소를 뽑았을 때 그 수가 특정 소인수를 포함하고 있을 확률은 50% 이상이다.

 

따라서, 위와 같은 원소 뽑기를 충분히 많이 반복하면 답이 되는 소인수를 포함하는 경우가 나오지 않을 확률은 0에 수렴하게 된다.

 

위의 관찰을 이용하여 충분히 많은 횟수의 원소를 뽑아 해당 수의 소인수들이 특정 소인수가 될 수 있는지 판단해 문제를 해결하자.

 

이 과정에서 이미 확인한 소인수를 다시 확인할 필요는 없으므로, 중복된 확인을 하지 않기 위한 최적화를 같이 진행해주자. 방법은 다양하지만 글쓴이는 주어진 원소에서 확인한 소인수는 나누어주는 방식으로 구현하였다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <random>
using namespace std;

bool sieve[32768];
vector<int> vec, ans;

void init() {
    sieve[0] = sieve[1] = 1;
    for (int i = 2; i * i < 32768; i++) {
        if (sieve[i]) continue;
        for (int j = i * i; j < 32768; j += i) sieve[j] = 1;
    }
    for (int i = 2; i < 31622; i++) {
        if (!sieve[i]) vec.emplace_back(i);
    }
}

int N;
int A[500000], AA[500000];
random_device rd;
mt19937 mt(rd());

void func(int i) {
    int cnt = 0;
    for (int k = 0; k < N; k++) {
        if (!(AA[k] % i)) {
            cnt++;
            while (!(AA[k] % i)) AA[k] /= i;
        }
    }
    if (cnt >= (N + 1) / 2) {
        cout << "YES\n";
        cnt = (N + 1) / 2;
        for (int k = 0; k < N && cnt; k++) {
            if (!(A[k] % i)) cnt--, cout << A[k] << ' ';
        }
        exit(0);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    init();

    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) AA[i] = A[i];
    for (int _ = 0; _ < 40; _++) {
        int x = AA[mt() % N];
        for (auto &i:vec) {
            if (i * i > x) break;
            if (x % i) continue;
            func(i);
            while (!(x % i)) x /= i;
        }
        if (x > 1) func(x);
    }

    cout << "NO";
}