백준 27470 (C++) 멋진 부분집합

최초 업로드: 2025-10-30 01:50:43

최근 수정 시간: 2025-10-30 01:50:43

게시자: rlatjwls3333

카테고리: 백준

# [Platinum IV] 멋진 부분집합

[문제 링크](https://www.acmicpc.net/problem/27470)

## 문제 설명

KSA 학생들은 멋진 집합을 좋아한다. 멋진 집합이란 모든 원소들의 최대공약수가 $1$보다 큰 정수들의 중복집합이다. 크기가 $N$인 중복집합이 주어졌을 때, 주어진 중복집합의 부분집합 중 크기가 $\left\lceil\cfrac{N}{2}\right\rceil$인 멋진 집합을 찾아보자!

## 입력

첫 번째 줄에 정수 $N$이 주어진다.

두 번째 줄에 중복집합의 원소들인 $N$개의 정수가 주어진다.

## 출력

첫 번째 줄에 멋진 집합이 존재한다면 <code>YES</code>, 아니라면 <code>NO</code>를 출력한다.

만약 멋진 집합이 존재한다면, 두 번째 줄에 멋진 집합에 속한 $\left\lceil\cfrac{N}{2}\right\rceil$개의 정수를 출력한다.

정답이 여러 개 존재한다면 아무거나 출력해도 상관없으며, 각 원소를 출력하는 순서는 상관없다.

## 제한
<ul>
	<li>$3 \leq N \leq 5 \times 10^{5}$</li>
	<li>주어지는 중복집합의 원소들은 $2$ 이상 $10^{9}$ 이하의 정수</li>
</ul>

## 풀이
멋진 집합이 존재한다면 어떤 원소를 선택했을 때, 멋진 집합에 속한 원소일 확률이 0.5이기 때문에, 랜덤하게 10개의 모든 소인수에 대해 멋진 집합이 있는지 판별을 하면 $1-0.5^{10}$의 확률로 통과합니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int n;
int a[500'000], original[500'000];

bool chk(int i) {
 int cnt=0;
 for(int k=0;k<n;k++) {
 if(a[k]%i==0) cnt++;
 while(a[k]%i==0) a[k]/=i;
 }
 if(cnt>=(n+1)/2) {
 cnt=(n+1)/2;
 cout << "YES\n";
 for(int k=0;k<n;k++) {
 if(original[k]%i==0 && cnt-->0) cout << original[k] << ' ';
 }
 return true;
 }
 return false;
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 cin >> n;
 for(int i=0;i<n;i++) {
 cin >> a[i];
 original[i]=a[i];
 }
 random_shuffle(a, a+n);

for(int i=0;i<min(n, 10);i++) {
 for(int j=2;j*j<=a[i];j++) {
 if(a[i]%j==0 && chk(j)) return 0;
 }
 if(a[i]!=1 && chk(a[i])) return 0;
 }
 cout << "NO";
}
```