B41 - Reverse of Euclid Editorial /

Time Limit: 10 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

変数 x, y があり、最初は両方の値が 1 です。以下の 2 種類の操作を何回か行うことで、変数 x の値を X, 変数 y の値を Y にする方法を求めてください。

  • x の値を x + y に変更する
  • y の値を x + y に変更する

ただし X と Y の最大公約数は 1 であるとします。

制約

  • 1 \leq X, Y \leq 10^6
  • X と Y の最大公約数は 1 である

入力

入力は以下の形式で標準入力から与えられます。 

X Y

出力

以下の形式で出力してください。

K
x_1 y_1
x_2 y_2
\vdots
x_K y_K

ここで、K は操作回数、x_i, y_i は i 回目の操作後の x, y の値を表します。

入力例 1

5 2

出力例 1

3
1 2
3 2
5 2
  • 1 回目の操作では y の値を x + y に変更します。x, y は 1, 2 になります
  • 2 回目の操作では x の値を x + y に変更します。x, y は 3, 2 になります
  • 3 回目の操作では x の値を x + y に変更します。x, y は 5, 2 になります

入力例 2

1 1

出力例 2

0