| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 20 초 | 256 MB | 37 | 12 | 8 | 36.364% |
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$.
The first line of input contains a single integer $t,ドル the number of test cases (1ドル \leq t \leq 10^5$).
For each test case, you may ask at most 10ドル$ queries. Each query should be one of two types:
It is guaranteed that the number $x$ in each test case does not change during testing.
3 1 500000004 2
? 1000000007 ! 1 1 ? 1000000007 ! 2 4 ? 1000000007 ! 2 1
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$.