From Modular to Rational

p, q가 각각 10^9 이하인 숨은 유리수 p/q를 알아내야 한다. 10^9보다 큰 소수 m을 골라 p·q^(-1) mod m을 묻는 질의를 10번까지 할 수 있다.

어려움9정수론수학구현완전 탐색아직 제출이 없습니다시간 제한20초메모리 제한256 MB

문제 설명

예제1

문제

This is an interactive problem.

Someone picked a positive rational number $x=p/q$ where $1 \leq p, q \leq 10^9$ . You may ask at most $10$ queries of the kind "? $m$ ", where $10^9 < m < 10^{12}$ and $m$ is a prime number. For each query, you will get the number $y$ such that $y \equiv pq^{-1} \pmod{m}$ . You have to guess the number $x$ .

힌트

In the example, you deal with $x=1/1$ , $x=1/2$ , and $x=2/1$ , while always taking $m=10^9+7$ .

As you may see, it is not necessary to have $\gcd(p,q)=1$ as long as $1\leq p,q\leq 10^9$ and $x=p/q$ .