BOJ 3501 최대공약수 맞추기 게임

문제 링크입니다.

문제 요약

$N$ 이하의 양의 정수 $x$를 최소한의 질문으로 알아내야 합니다. 질문을 통해 원하는 $y$에 대한 $\gcd (x, y)$를 알아낼 수 있습니다.

풀이

질문으로 소수 $p$를 보내면, 답변에 따라 후보를 ${1 \over p}$또는 ${p-1 \over p}$로 줄일 수 있습니다. $p \ge 2$임으로부터 ${p-1 \over p} \ge 1 {\over p}$를 얻으므로, 최대공약수가 1인 쪽이 맞히기 더 어렵습니다. 즉 맞히기 가장 어려운 수는 항상 1입니다.

1을 최대한 빨리 맞히는 전략을 찾으면 됩니다. 이를 위해서는 최소한의 질문 안에 $N$ 이하의 모든 소수를 질문할 수 있어야 합니다. 유니온-파인드적 감성으로 문제를 바라보면, 최대한 많은 소수를 다른 소수에 귀속시켜야 합니다. 이를 위해서는 최대한 많은 작은 소수를 큰 소수에 매칭시켜야 함을 알 수 있습니다.

투 포인터 등을 이용해 큰 소수부터 역순으로 훑으면서 작은 소수를 곱할 수 있는 대로 곱하는 방식으로 질문을 구성하는 것이 정당합니다. 체 등으로 범위 내 소수의 리스트를 얻은 뒤 이를 구현해 주면 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
int n; bool isp[12345]={1,1};
vector<int> p;
int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	cin >> n; for(int i = 2; i <= n; i++){
		if(!isp[i]){
			p.push_back(i);
			for(int j = i*i; j <= n; j+=i) isp[j] = 1;
		}
	}
	int ans = 0, l = 0, r = p.size();
	while(l < r){
		ans++; r--;
		int t = p[r];
		while(l < r && t*p[l] <= n) t *= p[l++];
	}
	cout << ans;
}