← 返回题目列表

Codeforces · 2234/A

A. 欧几里得、数列和两个数

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

我们为两个正整数 $$$x \geq y$$$ 定义长度为 $$$k$$$ ($$$k \geq 2$$$) 的欧几里得算法序列,如下正整数序列:

  • $$$a_1, a_2, \ldots, a_k$$$,其中 $$$a_1 = x$$$, $$$a_2 = y$$$,并且对于任何 $$$i$$$ ($$$1 \leq i \leq k - 2$$$),等式 $$$a_{i + 2} = (a_i \bmod a_{i + 1})$$$ 包含$$$^{\text{*}}$$$。

例如,对于$$$x = 13, y = 8, k = 4$$$,对应的欧几里得算法序列为$$$a = [13, 8, 5, 3]$$$。 ($$$a_3 = 13 \bmod 8 = 5$$$,$$$a_4 = 8 \bmod 5 = 3$$$)。

给定一个序列 $$$b_1, b_2, \ldots, b_n$$$。您需要确定是否可以排列其元素,使其成为两个正整数 $$$x \geq y$$$ 的欧几里得算法序列。

$$$^{\text{*}}$$$$$$x \bmod y$$$ 表示 $$$x$$$ 除以 $$$y$$$ 的余数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 100$$$) — 序列的大小。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 10^9$$$) — 序列 $$$b$$$。

输出

对于每个测试用例,如果可以排列序列 $$$b$$$ 的元素,以便存在一对合适的正整数 $$$x \geq y$$$,则在单独的行上输出 $$$x, y$$$。否则,在单独的行上输出 $$$-1$$$。

如果有几个合适的对 $$$x, y$$$,你可以输出其中任何一个。

示例

输入
复制

6
2
1 1
2
1 2
4
1 2 3 4
3
6 4 2
4
3 8 13 5
3
1 1 1

输出
复制

1 1
2 1
-1
6 4
13 8
-1

注意

在第一个测试用例中,对 ($$$1, 1$$$) 是合适的:对于 $$$x = 1, y = 1, k = 2$$$, $$$a_1 = x = 1, a_2 = y = 1$$$,并获得序列 $$$a = [1, 1] = b$$$。

在第三个测试用例中,可以证明不存在合适的对 ($$$x, y$$$)。

在第四个测试用例中, ($$$6, 4$$$) 是合适的:对于 $$$x = 6, y = 4, k = 3$$$, $$$a_1 = x = 6, a_2 = y = 4, a_3 = (a_1 \bmod a_2) = (6 \bmod 4) = 2$$$,以及序列 $$$a = [6, 4, 2] = b$$$ 得到。