305598: CF1060H. Sophisticated Device

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Sophisticated Device

题意翻译

## 题目描述 给你两个正整数 $d$ 和 $p$,$p$ 是质数。 你还有一个神奇的机器,有很多个格子,每个格子有一个 0 到 $p-1$ 的整数。它还支持两种操作:求和与求 $d$ 次幂。 **结果都对 $p$ 取模。** 这些格子编号分别为 $1,2,3,\ldots,5000$,一开始第一、二个格子分别存储 $x,y(0\leq x,y\leq p-1)$,其余格子存储 1。 你不能直接访问格子里面的变量,你也**不知道** $x,y$ 为多少(但你知道它们分别存在前两格)。你应该使用给定的指令编写程序,让一个格子里面出现 $xy\mod p$。你的程序必须可以应对任何可能的 $x,y$。 加法指令把两个格子里面的数之和放进第三个格子。这个指令形如 `+ e1 e2 to`,用途是将第 $e1$ 格与第 $e2$ 格之和放入第 $to$ 格。$e1,e2,to$ 可以相等。 第二个指令将一个格子里的数的 $d$ 次幂放进另一个格子。这个指令形如 `^ e to`,用途是将第 $e$ 格数字的 $d$ 次幂放入第 $to$ 格。$e,to$可以相等,这时第 $e$ 格的数字将被覆盖。 最后一个指令返回答案。这个指令形如 `f target`,用途是表示第 $target$ 格就是所求的 $xy\mod p$。这之后不应有任何指令。 编写程序求出 $xy\mod p$。指令总数不应超过 5000 条,包括返回答案的指令在内。 保证有解。 ## 输入输出格式 ### 输入格式 第一行两个正整数 $d,p$,用空格隔开。($2\leq d\leq 10,d<p,3 \leq p \leq 10^9 + 9$,$p$ 为质数) ## 说明 本题**没有样例**。下面是个例子。注意这不是任何一个数据的解,仅仅为了说明格式。 ```text + 1 1 3 ^ 3 3 + 3 2 2 + 3 2 3 ^ 3 1 f 1 ``` 下面是分步说明: |步骤 |格1 |格2 |格3 | | :-----------: | :-----------: | :-----------: | :-----------: | |最初 |$x$ |$y$ |$1$ | |`+ 1 1 3`|$x$ |$y$ |$2x$ | |`^3 3` |$x$ |$y$ |$(2x)^d$ | |`+3 2 2` |$x$ |$y+(2x)^d$ |$(2x)^d$ | |`+ 3 2 3` |$x$ |$y+(2x)^d$ |$y+2*(2x)^d$ | |`^ 3 1` |$(y+2*(2x)^d)^d$ |$y+(2x)^d$ |$y+2*(2x)^d$ |

题目描述

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.

输入输出格式

输入格式


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.

Input

题意翻译

## 题目描述 给你两个正整数 $d$ 和 $p$,$p$ 是质数。 你还有一个神奇的机器,有很多个格子,每个格子有一个 0 到 $p-1$ 的整数。它还支持两种操作:求和与求 $d$ 次幂。 **结果都对 $p$ 取模。** 这些格子编号分别为 $1,2,3,\ldots,5000$,一开始第一、二个格子分别存储 $x,y(0\leq x,y\leq p-1)$,其余格子存储 1。 你不能直接访问格子里面的变量,你也**不知道** $x,y$ 为多少(但你知道它们分别存在前两格)。你应该使用给定的指令编写程序,让一个格子里面出现 $xy\mod p$。你的程序必须可以应对任何可能的 $x,y$。 加法指令把两个格子里面的数之和放进第三个格子。这个指令形如 `+ e1 e2 to`,用途是将第 $e1$ 格与第 $e2$ 格之和放入第 $to$ 格。$e1,e2,to$ 可以相等。 第二个指令将一个格子里的数的 $d$ 次幂放进另一个格子。这个指令形如 `^ e to`,用途是将第 $e$ 格数字的 $d$ 次幂放入第 $to$ 格。$e,to$可以相等,这时第 $e$ 格的数字将被覆盖。 最后一个指令返回答案。这个指令形如 `f target`,用途是表示第 $target$ 格就是所求的 $xy\mod p$。这之后不应有任何指令。 编写程序求出 $xy\mod p$。指令总数不应超过 5000 条,包括返回答案的指令在内。 保证有解。 ## 输入输出格式 ### 输入格式 第一行两个正整数 $d,p$,用空格隔开。($2\leq d\leq 10,d<p,3 \leq p \leq 10^9 + 9$,$p$ 为质数) ## 说明 本题**没有样例**。下面是个例子。注意这不是任何一个数据的解,仅仅为了说明格式。 ```text + 1 1 3 ^ 3 3 + 3 2 2 + 3 2 3 ^ 3 1 f 1 ``` 下面是分步说明: |步骤 |格1 |格2 |格3 | | :-----------: | :-----------: | :-----------: | :-----------: | |最初 |$x$ |$y$ |$1$ | |`+ 1 1 3`|$x$ |$y$ |$2x$ | |`^3 3` |$x$ |$y$ |$(2x)^d$ | |`+3 2 2` |$x$ |$y+(2x)^d$ |$(2x)^d$ | |`+ 3 2 3` |$x$ |$y+(2x)^d$ |$y+2*(2x)^d$ | |`^ 3 1` |$(y+2*(2x)^d)^d$ |$y+(2x)^d$ |$y+2*(2x)^d$ |

加入题单

上一题 下一题 算法标签: