A12092. Sophisticated Device
编程题
普及/提高-
知识点
题目描述
You are given integers $d$ and $p$ , $p$ is prime.
Also you have a mysterious device. It has memory cells, each contains an integer between $0$ and $p-1$ . Also two instructions are supported, addition and raising to the $d$ -th power. $\textbf{Both are modulo}$ $p$ .
The memory cells are numbered $1, 2, \dots, 5000$ . Initially cells $1$ and $2$ contain integers $x$ and $y$ , respectively ( $0 \leqslant x, y \leq p - 1$ ). All other cells contain $\textbf{1}$ s.
You can not directly access values in cells, and you $\textbf{don't know}$ values of $x$ and $y$ (but you know they are written in first two cells). You mission, should you choose to accept it, is to write a program using the available instructions to obtain the product $xy$ modulo $p$ in one of the cells. You program should work for all possible $x$ and $y$ .
Addition instruction evaluates sum of values in two cells and writes it to third cell. This instruction is encoded by a string "+ e1 e2 to", which writes sum of values in cells e1 and e2 into cell to. Any values of e1, e2, to can coincide.
Second instruction writes the $d$ -th power of a value in some cell to the target cell. This instruction is encoded by a string "^ e to". Values e and to can coincide, in this case value in the cell will be overwritten.
Last instruction is special, this is the return instruction, and it is encoded by a string "f target". This means you obtained values $xy \bmod p$ in the cell target. No instructions should be called after this instruction.
Provide a program that obtains $xy \bmod p$ and uses no more than $5000$ instructions (including the return instruction).
It is guaranteed that, under given constrains, a solution exists.
Also you have a mysterious device. It has memory cells, each contains an integer between $0$ and $p-1$ . Also two instructions are supported, addition and raising to the $d$ -th power. $\textbf{Both are modulo}$ $p$ .
The memory cells are numbered $1, 2, \dots, 5000$ . Initially cells $1$ and $2$ contain integers $x$ and $y$ , respectively ( $0 \leqslant x, y \leq p - 1$ ). All other cells contain $\textbf{1}$ s.
You can not directly access values in cells, and you $\textbf{don't know}$ values of $x$ and $y$ (but you know they are written in first two cells). You mission, should you choose to accept it, is to write a program using the available instructions to obtain the product $xy$ modulo $p$ in one of the cells. You program should work for all possible $x$ and $y$ .
Addition instruction evaluates sum of values in two cells and writes it to third cell. This instruction is encoded by a string "+ e1 e2 to", which writes sum of values in cells e1 and e2 into cell to. Any values of e1, e2, to can coincide.
Second instruction writes the $d$ -th power of a value in some cell to the target cell. This instruction is encoded by a string "^ e to". Values e and to can coincide, in this case value in the cell will be overwritten.
Last instruction is special, this is the return instruction, and it is encoded by a string "f target". This means you obtained values $xy \bmod p$ in the cell target. No instructions should be called after this instruction.
Provide a program that obtains $xy \bmod p$ and uses no more than $5000$ instructions (including the return instruction).
It is guaranteed that, under given constrains, a solution exists.
输入格式
The first line contains space-separated integers $d$ and $p$ ( $2 \leqslant d \leqslant 10$ , $d < p$ , $3 \leqslant p \leqslant 10^9 + 9$ , $p$ is prime).
输出格式
无
说明/提示
This problem has no sample tests. A sample output is shown below. Note that this output is not supposed to be a solution to any testcase, and is there purely to illustrate the output format.
$\texttt{+ 1 1 3}\\ \texttt{^ 3 3}\\ \texttt{+ 3 2 2}\\ \texttt{+ 3 2 3}\\ \texttt{^ 3 1}\\ \texttt{f 1}$
Here's a step-by-step runtime illustration:
$\begin{array}{|c|c|c|c|} \hline \texttt{} & \text{cell 1} & \text{cell 2} & \text{cell 3} \\<br /><br />\hline \text{initially} & x & y & 1 \\ \hline \texttt{+ 1 1 3} & x & y & 2x \\ \hline<br /><br />\texttt{^ 3 3} & x & y & (2x)^d \\ \hline<br /><br />\texttt{+ 3 2 2} & x & y + (2x)^d & (2x)^d \\ \hline<br /><br />\texttt{+ 3 2 3} & x & y + (2x)^d & y + 2\cdot(2x)^d \\ \hline<br /><br />\texttt{^ 3 1} & (y + 2\cdot(2x)^d)^d & y + (2x)^d & y + 2\cdot(2x)^d \\ \hline<br /><br />\end{array}$
Suppose that $d = 2$ and $p = 3$ . Since for $x = 0$ and $y = 1$ the returned result is $1 \neq 0 \cdot 1 \bmod 3$ , this program would be judged as incorrect.
$\texttt{+ 1 1 3}\\ \texttt{^ 3 3}\\ \texttt{+ 3 2 2}\\ \texttt{+ 3 2 3}\\ \texttt{^ 3 1}\\ \texttt{f 1}$
Here's a step-by-step runtime illustration:
$\begin{array}{|c|c|c|c|} \hline \texttt{} & \text{cell 1} & \text{cell 2} & \text{cell 3} \\<br /><br />\hline \text{initially} & x & y & 1 \\ \hline \texttt{+ 1 1 3} & x & y & 2x \\ \hline<br /><br />\texttt{^ 3 3} & x & y & (2x)^d \\ \hline<br /><br />\texttt{+ 3 2 2} & x & y + (2x)^d & (2x)^d \\ \hline<br /><br />\texttt{+ 3 2 3} & x & y + (2x)^d & y + 2\cdot(2x)^d \\ \hline<br /><br />\texttt{^ 3 1} & (y + 2\cdot(2x)^d)^d & y + (2x)^d & y + 2\cdot(2x)^d \\ \hline<br /><br />\end{array}$
Suppose that $d = 2$ and $p = 3$ . Since for $x = 0$ and $y = 1$ the returned result is $1 \neq 0 \cdot 1 \bmod 3$ , this program would be judged as incorrect.