백준 34162 (C++) NP=P

최초 업로드: 2025-08-25 03:20:35

최근 수정 시간: 2025-08-25 03:20:59

카테고리: 백준

# [Silver V] NP=P

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

## 문제 설명

이 문제는 인터랙티브 문제입니다.

동우와 세준이는 이항 계수 놀이를 만들었다.

이 놀이는 먼저 세준이가 양의 정수 $K$와 $K$ 이하의 양의 정수 $M$을 정한다. 그 후 세준이가 동우에게 $K$를 알려주면, 동우는 다음 질문을 최소로 하여 $M$을 맞춰야 한다.

<ul>
	<li>동우가 세준이에게 정수 $N$을 질문하면, 세준이는 $\binom{M}{\,N \bmod (M+1)} \bmod K$*를 알려준다.</li>
</ul>

동우를 도와 주어진 $K$에 대해 최악의 경우에도 $M$을 맞출 수 있는 질문 횟수의 최솟값을 찾고, 실제로 $M$을 맞춰보자.

<hr>
*$\binom{a}{b}$는 조합(combination)으로, $a$개의 공들 중 $b$개를 구분 없이 뽑는 경우의 수를 의미한다.

## 입력

컴퓨터는 세준이, 유저는 동우로 생각하고 인터랙티브가 진행된다.

먼저 컴퓨터가 유저에게 $K(1\le K\le 10^6)$를 입력으로 준다.

유저는 주어진 $K$에서 $M$을 맞출 수 있는 질문 횟수의 최솟값 $Q$를 출력한다. 만약 $Q$가 잘못되었다면 컴퓨터는 즉시 틀렸습니다를 띄우고 프로그램을 종료한다.

이후 유저와 컴퓨터는 아래 과정을 $Q$번 반복한다.

<ul>
	<li>유저는 정수 $N(0\le N\le 10^{18})$을 하나 출력한다.</li>
	<li>컴퓨터는 $\binom{M}{\,N \bmod (M+1)} \bmod K$를 입력으로 준다.</li>
</ul>

$Q$번의 질의가 끝난 후, 유저는 예측한 $M$을 출력한다.

조건을 만족하지 않거나 잘못된 출력을 하는 경우, 컴퓨터는 틀렸습니다를 띄우고 프로그램을 종료한다.

유저는 출력 후 다른 출력 없이 프로그램을 종료해야 한다.

인터랙션 도중 컴퓨터에게 정상적인 출력이 전달되지 않았거나 덜 전달된 경우, flush를 하지 않은 경우, 혹은 정답 출력 후 프로그램이 종료되지 않는 경우 등의 상황에는 시간 초과 등의 결과를 받을 수 있다.

## 풀이
#### K=1일 때는 질문을 하지 않아도 M이 1이라는 사실을 알 수 있고, 그 외에는 $\binom{M}{1} \bmod K$만 1번 질문해 M을 알아내면 된다.

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

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

if(k==1) {
 cout << "0\n1" << flush;
 } else {
 cout << "1\n1\n" << flush;
 int m; cin >> m;
 cout << (m+k-1)%k+1 << flush;
 }
}
```