English · Original
Chinese · Translation
Formal · Original
Allen is playing Number Clicker on his phone.
He starts with an integer $u$ on the screen. Every second, he can press one of 3 buttons.
1. Turn $u \to u+1 \pmod{p}$.
2. Turn $u \to u+p-1 \pmod{p}$.
3. Turn $u \to u^{p-2} \pmod{p}$.
Allen wants to press at most 200 buttons and end up with $v$ on the screen. Help him!
## Input
The first line of the input contains 3 positive integers: $u, v, p$ ($0 \le u, v \le p-1$, $3 \le p \le 10^9 + 9$). $p$ is guaranteed to be prime.
## Output
On the first line, print a single integer $\ell$, the number of button presses. On the second line, print integers $c_1, \dots, c_\ell$, the button presses. For $1 \le i \le \ell$, $1 \le c_i \le 3$.
We can show that the answer always exists.
[samples]
## Note
In the first example the integer on the screen changes as $1 \to 2 \to 3$.
In the second example the integer on the screen changes as $3 \to 2$.
[{"iden":"statement","content":"Allen 正在玩手机上的《数字点击器》游戏。\n\n他初始时屏幕上有一个整数 $u$。每一秒，他可以按下三个按钮中的一个。\n\nAllen 希望按下至多 200 个按钮后，屏幕上出现整数 $v$。请帮助他！\n\n输入的第一行包含三个正整数：$u, v, p$（$0 lt.eq u, v lt.eq p -1$，$3 lt.eq p lt.eq 10^9 + 9$）。$p$ 保证为质数。\n\n第一行输出一个整数 $ell$，表示按钮按下的次数。第二行输出 $c_1, dots.h, c_ell$，表示按钮的按下序列。对于 $1 lt.eq i lt.eq ell$，有 $1 lt.eq c_i lt.eq 3$。\n\n我们可以证明答案一定存在。\n\n在第一个例子中，屏幕上的整数变化为 $1 arrow.r 2 arrow.r 3$。\n\n在第二个例子中，屏幕上的整数变化为 $3 arrow.r 2$。 "},{"iden":"input","content":"输入的第一行包含三个正整数：$u, v, p$（$0 lt.eq u, v lt.eq p -1$，$3 lt.eq p lt.eq 10^9 + 9$）。$p$ 保证为质数。"},{"iden":"output","content":"第一行输出一个整数 $ell$，表示按钮按下的次数。第二行输出 $c_1, dots.h, c_ell$，表示按钮的按下序列。对于 $1 lt.eq i lt.eq ell$，有 $1 lt.eq c_i lt.eq 3$。我们可以证明答案一定存在。"},{"iden":"examples","content":"输入\n1 3 5\n输出\n2\n1 1\n\n输入\n3 2 5\n输出\n1\n3"},{"iden":"note","content":"在第一个例子中，屏幕上的整数变化为 $1 arrow.r 2 arrow.r 3$。在第二个例子中，屏幕上的整数变化为 $3 arrow.r 2$。 "}]*
**Definitions**
Let $ u, v \in \mathbb{Z} $ be the initial and target integers, respectively.
Let $ p $ be a prime modulus with $ p \geq 3 $.
Let $ x_0 = u $, and for each move $ i \in \{1, \dots, \ell\} $, the state evolves as:
- If $ c_i = 1 $: $ x_i = (x_{i-1} + 1) \bmod p $
- If $ c_i = 2 $: $ x_i = (x_{i-1} - 1) \bmod p $
- If $ c_i = 3 $: $ x_i = (x_{i-1} \cdot x_{i-1}) \bmod p $
**Constraints**
1. $ 0 \leq u, v < p $
2. $ 3 \leq p \leq 10^9 + 9 $, $ p $ prime
3. $ \ell \leq 200 $
4. For all $ i \in \{1, \dots, \ell\} $, $ c_i \in \{1, 2, 3\} $
5. $ x_\ell \equiv v \pmod{p} $
**Objective**
Find a sequence $ (c_1, c_2, \dots, c_\ell) $ of button presses such that applying the above operations starting from $ u $ yields $ v \mod p $, with $ \ell \leq 200 $.
API Response (JSON)
{
"problem": {
"name": "E. Number Clicker",
"description": {
"content": "Allen is playing Number Clicker on his phone. He starts with an integer $u$ on the screen. Every second, he can press one of 3 buttons. 1. Turn $u \\to u+1 \\pmod{p}$. 2. Turn $u \\to u+p-1 \\pmod{p}$",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 5000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF995E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Allen is playing Number Clicker on his phone.\n\nHe starts with an integer $u$ on the screen. Every second, he can press one of 3 buttons.\n\n1. Turn $u \\to u+1 \\pmod{p}$.\n2. Turn $u \\to u+p-1 \\pmod{p}$...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"Allen 正在玩手机上的《数字点击器》游戏。\\n\\n他初始时屏幕上有一个整数 $u$。每一秒，他可以按下三个按钮中的一个。\\n\\nAllen 希望按下至多 200 个按钮后，屏幕上出现整数 $v$。请帮助他！\\n\\n输入的第一行包含三个正整数：$u, v, p$（$0 lt.eq u, v lt.eq p -1$，$3 lt.eq ...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ u, v \\in \\mathbb{Z} $ be the initial and target integers, respectively. \nLet $ p $ be a prime modulus with $ p \\geq 3 $. \nLet $ x_0 = u $, and for each move $ i \\in \\{1, \\dot...",
"is_translate": false,
"language": "Formal"
}
]
}