{"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}$.\n3.  Turn $u \\to u^{p-2} \\pmod{p}$.\n\nAllen wants to press at most 200 buttons and end up with $v$ on the screen. Help him!\n\n## Input\n\nThe 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.\n\n## Output\n\nOn 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$.\n\nWe can show that the answer always exists.\n\n[samples]\n\n## Note\n\nIn the first example the integer on the screen changes as $1 \\to 2 \\to 3$.\n\nIn the second example the integer on the screen changes as $3 \\to 2$.","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 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$。 \"}]*","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, \\dots, \\ell\\} $, the state evolves as:  \n- If $ c_i = 1 $: $ x_i = (x_{i-1} + 1) \\bmod p $  \n- If $ c_i = 2 $: $ x_i = (x_{i-1} - 1) \\bmod p $  \n- If $ c_i = 3 $: $ x_i = (x_{i-1} \\cdot x_{i-1}) \\bmod p $  \n\n**Constraints**  \n1. $ 0 \\leq u, v < p $  \n2. $ 3 \\leq p \\leq 10^9 + 9 $, $ p $ prime  \n3. $ \\ell \\leq 200 $  \n4. For all $ i \\in \\{1, \\dots, \\ell\\} $, $ c_i \\in \\{1, 2, 3\\} $  \n5. $ x_\\ell \\equiv v \\pmod{p} $  \n\n**Objective**  \nFind 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 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF995E","tags":["divide and conquer","graphs","meet-in-the-middle","number theory"],"sample_group":[["1 3 5","2\n1 1"],["3 2 5","1\n3"]],"created_at":"2026-03-03 11:00:39"}}