No.3522 Power of Power
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.
- 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$.
- 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:
- First, choose non-negative integers $i$ and $j$ not exceeding $10^9$, and output
?, $i$, and $j$ separated by single spaces on $1$ line. - 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\})$.
? $i$ $j$
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。