34162번 - NP=P 서브태스크인터랙티브

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

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

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

• 동우가 세준이에게 정수 $N$을 질문하면, 세준이는 $\dbinom{M}{N\bmod{\left( M+1 \right)}}\bmod K$^*를 알려준다.

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

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

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

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

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

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

• 유저는 정수 $N(0\le N\le 10^{18})$을 하나 출력한다.
• 컴퓨터는 $\dbinom{M}{N\bmod{\left( M+1 \right)}}\bmod K$를 입력으로 준다.

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

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

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

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