← 返回题目列表

AtCoder · tessoku_book_dn

B41. 欧几里得的逆面

中文机器翻译题面 查看原题

配点: 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