305238: CF995E. Number Clicker

Memory Limit:256 MB Time Limit:5 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Number Clicker

题意翻译

小y在玩数学游戏,他有三种变化方式,(1)将该数+1,(2)将该数-1,(3)将该数变成他的逆元(即p-2次幂),当然,我们所以操作都是在mod p意义下的 现在小h知道了变换前的数u和变换后的数v,给定模数p保证是质数,他想知道怎么在200次操作之内得到v

题目描述

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!

输入输出格式

输入格式


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.

输出格式


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.

输入输出样例

输入样例 #1

1 3 5

输出样例 #1

2
1 1

输入样例 #2

3 2 5

输出样例 #2

1
3

说明

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 $ .

Input

题意翻译

小y在玩数学游戏,他有三种变化方式,(1)将该数+1,(2)将该数-1,(3)将该数变成他的逆元(即p-2次幂),当然,我们所以操作都是在mod p意义下的 现在小h知道了变换前的数u和变换后的数v,给定模数p保证是质数,他想知道怎么在200次操作之内得到v

加入题单

上一题 下一题 算法标签: