35066번 - 과제 해결하기 2 인터랙티브

문제

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

경기과학고등학교 정수론 수업에서는 학생들의 실력을 평가하기 위한 수행평가를 진행한다. 수행평가 문제의 내용은 다음과 같다.

선생님은 1ドル \le N \le 10^{12}$ 범위의 정수 $N$ 하나를 미리 정해 두었다. 학생들은 제한된 형태의 질문을 통해 $N$을 알아낸 뒤 정답을 제출해야 한다. 선생님은 학생들이 정수론 개념을 제대로 이해했는지 확인하기 위해, 정수 $N$에 대해 할 수 있는 질문과 답안 제출 형식을 다음과 같이 제한하였다.

• ? $m$ $r$: $N$의 양의 약수들 중 $m$으로 나눈 나머지가 $r$인 것의 개수를 질문한다.
• ! $N$: $N$을 정답으로 제출한다.

각 학생의 질문 횟수는 최대 300ドル$번으로 제한되어 있으며, 정답은 한 번 제출하면 수정할 수 없다.

정수론을 수강하는 경곽이는 여러 전략을 구상했지만, 주어진 질문 횟수 안에 $N$을 찾아내는 방법을 알아내지 못하였다. 어느덧 제출 기한이 코앞까지 다가온 경곽이는 수행평가를 무사히 완료하기 위해 여러분에게 도움을 요청하였다. 경곽이가 수행평가를 제시간 안에 제출할 수 있도록 도와주자.

입력

출력

제한

인터랙션

여러분은 아래의 질문을 최대 300ドル$번 할 수 있다.

• ? $m$ $r$: $N$의 양의 약수 중 $m$으로 나눈 나머지가 $r$인 것의 개수를 물어본다. 2ドル \leq m \leq 10^{18}$ 및 0ドル \leq r < m$을 만족해야 하며, 만족하지 않을 경우 를 받는다.

만약, 충분한 질문을 통해서 선생님이 정한 정수 $N$을 찾았다면, 아래와 같이 정답을 제출할 수 있다.

• ! $N$

각 출력 후에는 표준 출력 버퍼를 비워야 한다. 정답을 말한 후에는 추가적인 출력 없이 프로그램을 종료해야 한다. 위의 조건을 만족하지 않는 비정상적인 출력으로 질문할 경우, 잘못된 입력을 주거나, 혹은 등 의도되지 않은 결과가 나올 수 있음에 유의하라.

그레이더는 비적응적이다. 즉, 초기에 그레이더는 $N$을 하나 정해 두고 사용자가 질문할 때 맨 처음에 정한 $N$에 따라 답변한다.

노트

언어별로 표준 출력 버퍼를 비우는 방법은 다음과 같다.

• C: fflush(stdout)
• C++: std::cout << std::flush
• Java: System.out.flush()
• Python: sys.stdout.flush()