No.3570 Blackbox Modular Arithmetic
Problem Statement
This is an interactive problem.
In this problem, each input contains $T$ test cases.
Problem summary:
The elements of the residue class ring $\mathbb{Z}/N\mathbb{Z}$ are arranged on a circle.
However, $N$ is not given, and each element is assigned a random value.
You may ask up to $Q$ times for a power of the sum of $2$ elements, and you must identify the value corresponding to $1$.
Here, each of the $2$ elements is specified by its position, counted clockwise from the value corresponding to $0$.
Formal statement:
There is a positive integer $N$. $N$ is hidden by the judge.
The judge generates a permutation $A$ and a sequence of non-negative integers $B$ by the following procedure. The generated $A$ and $B$ are fixed for each test case and do not change.
- Generate a permutation $\left(A_0,A_1,\dots,A_{N-1}\right)$ of $\left(0,1,\dots,N-1\right)$ such that $A_0=0$, and let it be $A$.
- Generate a sequence $(B_0,B_1,\dots,B_{N-1})$ of non-negative integers not exceeding $10^9$ such that all $B_i,(0\le i<N)$ are distinct, and let it be $B$.
You may ask the following query up to $Q$ times.
- Specify a triple of integers $(i,j,k)$ satisfying $0\le i\le 10^9,\,0\le j\le 10^9,\,2\le k\le 10^9$. The judge outputs $B_x$, where $x=\left(A_{i\bmod N}+A_{j\bmod N}\right)^k\bmod N$. Here, $a\bmod N$ is the remainder when $a$ is divided by $N$.
Identify $B_1$.
Constraints
- All inputs are integers.
- $1\le T\le 5$
- $2\le N\le 10^6$
- $Q=1600$
Input and Output
First, the number of test cases $T$ is given from standard input.
$T$
After that, $T$ test cases follow.
You may ask queries. Print each query to standard output in the following format.
? $i$ $j$ $k$
The response to a query is given from standard input in the following format.
$B_x$
However, if the format or constraints of the query are violated, or if the number of queries exceeds $Q$, -1 is given from standard input instead. In this case, terminate your program immediately.
Once you have identified $B_1$, print it to standard output in the following format.
! $B_1$
After that, proceed to the next test case if there is one; otherwise, terminate your program immediately.
Print a newline at the end of each output and flush standard output.
Sample
For $T=2$, the following interaction is possible.
| Input | Output | Explanation |
|---|---|---|
| 2 | The number of test cases $T=2$ is given. | |
| The $1$st test case starts. Suppose $N=5,\,A=(0,2,3,4,1),\,B=(4,3,2,1,0)$. | ||
| ? $1$ $2$ $2$ | Ask a query with $(i,j,k)=(1,2,2)$. | |
| $4$ | Since $x=(A_{1}+A_{2})^2\bmod N=0$, $B_0=4$ is output. | |
| ? $5$ $6$ $8$ | Ask a query with $(i,j,k)=(5,6,8)$. | |
| $3$ | Since $x=\left(A_{0}+A_{1}\right)^8\bmod N=1$, $B_1=3$ is output. | |
| ! $3$ | Print the identified value $B_1=3$. | |
| The $2$nd test case starts. Suppose $N=2,\,A=(0,1),\,B=(10,9)$. | ||
| ? $0$ $1$ $100$ | Ask a query with $(i,j,k)=(0,1,100)$. | |
| $9$ | Since $x=\left(A_{0}+A_{1}\right)^{100}=1$, $B_1=9$ is output. | |
| ! $9$ | Print the identified value $B_1=9$. |
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
hamamu