問題一覧 > 通常問題

No.3570 Blackbox Modular Arithmetic

レベル : / AI推定難易度 : 2900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / リアクティブ問題 (詳しくはこちら)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 2
作問者 : 👑 to-omer / テスター : 👑 hamamu
お気に入りにしたユーザー ProblemId : 9893 / 自分の提出
問題文最終更新日: 2026-04-18 14:10:30
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 501 (順位表) の他の問題:

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.

InputOutputExplanation
2The 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もしくは右上の雲マークをクリックしてアカウントを作成してください。