問題一覧 > 教育的問題

No.3522 Power of Power

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら)
タグ : (AC するまで非表示) / 解いたユーザー数 25
作問者 : 👑 p-adic / テスター : 👑 binap
お気に入りにしたユーザー ProblemId : 10976 / 自分の提出
問題文最終更新日: 2025-02-10 12:51:45
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 498 リアクティブコンテスト (順位表) の他の問題:

Problem Statement

This is a reactive problem (your program must run interactively with the judge's program).

 

First, $3$ non-negative integers $N, M, L$ are given.

 

Power-Loving Bot is a bot that loves powers.

Power-Loving Bot secretly holds a positive integer $B$ and wants to know the remainder $N^{(M^L)} \bmod B$ when $N^{(M^L)}$ ($N$ raised to the power of "$M$ to the power of $L$") is divided by $B$.

Here, $0^0$ is defined to be $1$.

 

So, you may perform the following query any number of times between $0$ and $100$, inclusive.

  1. First, you choose non-negative integers $i$ and $j$ not exceeding $10^9$, and ask for the remainder $i^j \bmod B$ when $i^j$ is divided by $B$.
  2. Then, Power-Loving Bot answers with $i^j \bmod B$.

Finally, find $N^{(M^L)} \bmod B$.

Input and Output

First, $N, M, L$ are given separated by single spaces on $1$ line from standard input.

$N$ $M$ $L$

After that, perform queries any number of times between $0$ and $100$, inclusive. Queries are made using standard input and output in the following format:

  1. First, choose non-negative integers $i$ and $j$ not exceeding $10^9$, and output ?, $i$, and $j$ separated by single spaces on $1$ line.
  2. ? $i$ $j$
    
  3. Then, $i^j \bmod B$ is given on $1$ line. The judge's time complexity for this is guaranteed to be $O(\log_2 \max \{1,j\})$.
  4. $i^j \bmod B$
    

Next, output your answer to this problem to standard output in the following format:

  • Output ! and $N^{(M^L)} \bmod B$ separated by a single space on $1$ line.
  • ! $N^{(M^L)} \bmod B$
    

Finally, print a newline.

Constraints

Although not given in the input, $B$ satisfies the following constraints:

  • $B$ is fixed before all queries; that is, the value of $B$ does not change before or after a query.
  • $B$ is an integer satisfying $1 \leq B \leq 10^9$.

The input satisfies the following constraints:

  • $N$ is an integer satisfying $0 \leq N \leq 10^2$.
  • $M$ is an integer satisfying $0 \leq M \leq 10^2$.
  • $L$ is an integer satisfying $0 \leq L \leq 10^2$.
  • For any non-negative integers $i, j$ not exceeding $10^9$, the input $i^j \bmod B$ given as the response when asking for the remainder of $i^j$ divided by $B$ is an integer satisfying $0 \leq i^j \bmod B < B$.

Notes

If you are not familiar with reactive problems, please also refer to the summary on reactive problems.

In this problem, the judge result is not guaranteed for submissions that do not follow the instructions below:

  • Strictly follow the specified output format. For example, do not insert extra spaces.
  • Each time you output, add a newline at the end and flush standard output.
  • Terminate your program immediately after outputting your answer to this problem.

Sample

The following is an example of the interaction when Power-Loving Bot secretly holds $B = 10$.

Input Output Explanation
4 3 2 $(N,M,L) = (4,3,2)$ is given as input.
? 0 0 You asked for the remainder of $0^0$ divided by $B$.
1 Power-Loving Bot answered that the remainder of $0^0 = 1$ divided by $B = 10$ is $1$.
? 5 2 You asked for the remainder of $5^2$ divided by $B$.
5 Power-Loving Bot answered that the remainder of $5^2 = 25$ divided by $B = 10$ is $5$.
? 2 5 You asked for the remainder of $2^5$ divided by $B$.
2 Power-Loving Bot answered that the remainder of $2^5 = 32$ divided by $B = 10$ is $2$.
? 10 1 You asked for the remainder of $10^1$ divided by $B$.
0 Power-Loving Bot answered that the remainder of $10^1 = 10$ divided by $B = 10$ is $0$.
? 4 9 You asked for the remainder of $4^9$ divided by $B$.
4 Power-Loving Bot answered that the remainder of $4^9 = 262144$ divided by $B = 10$ is $4$.
! 4 You answered that the remainder of $N^{(M^L)} = 4^{(3^2)}$ divided by $B = 10$ is $4$. This is correct.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。