← 返回题目列表

Codeforces · 1684/G

G. 欧几里得猜测

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

让我们考虑一下寻找最大公约数的欧几里得算法,其中 $$$t$$$ 是一个列表:

有一个数组 $$$p$$$,由不大于 $$$m$$$ 的正整数对组成。最初,列表 $$$t$$$ 是空的。然后该函数在 $$$p$$$ 中的每一对上运行。之后,列表 $$$t$$$ 会被打乱并提供给您。

你必须找到一个大小不大于 $$$2 \cdot 10^4$$$ 的数组 $$$p$$$ 来生成给定列表 $$$t$$$,或者告诉不存在这样的数组。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 10^3$$$, $$$1 \le m \le 10^9$$$) - 数组 $$$t$$$ 的长度和成对整数的约束。

第二行包含 $$$n$$$ 整数 $$$t_1, t_2, \ldots, t_n$$$ ($$$1 \le t_i \le m$$$) — 数组 $$$t$$$ 的元素。

输出

- 如果答案不存在,则输出$$$-1$$$。
- 如果答案存在,则在第一行输出 $$$k$$$ ($$$1 \le k \le 2 \cdot 10^4$$$) - 数组 $$$p$$$ 的大小,i。 e.答案中的对数。接下来的 $$$k$$$ 行中的第 $$$i$$$ 应包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le m$$$) — $$$p$$$ 中的第 $$$i$$$ 对。

如果有多个有效答案,您可以输出其中任何一个。

示例

输入 #1

7 20
1 8 1 6 3 2 3

输出 #1

3
19 11
15 9
3 7

输入 #2

2 10
7 1

输出 #2

-1

输入 #3

2 15
1 7

输出 #3

1
15 8

输入#4

1 1000000000
845063470

输出#4

-1

注意

在第一个示例中,我们考虑每对的数组 $$$t$$$:

- $$$(19,\, 11)$$$: $$$t = [8, 3, 2, 1]$$$;
- $$$(15,\, 9)$$$: $$$t = [6, 3]$$$;
- $$$(3,\, 7)$$$:$$$t = [1]$$$。

因此总共 $$$t = [8, 3, 2, 1, 6, 3, 1]$$$,与输入 $$$t$$$ 相同(最多排列)。

在第二个测试用例中,不可能找到所有整数不大于 $$$10$$$ 并且 $$$t = [7, 1]$$$ 的数组 $$$p$$$

在 $$$(15,\, 8)$$$ 数组的第三个测试用例中,$$$t$$$ 将为 $$$[7, 1]$$$。