← 返回题目列表

Codeforces · 2085/E

E. Serval 和 Modulo

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

有一个数组$$$a$$$,由$$$n$$$非负整数和a组成 幻数 $$$k$$$ ($$$k\ge 1$$$,$$$k$$$ 是一个整数)。 Serval 构造了另一个长度为 $$$n$$$ 的数组 $$$b$$$,其中 $$$b_i = a_i \bmod k$$$ 为所有 $$$1\leq i\leq n$$$ 保存了$$$^{\text{*}}$$$。然后,他 已洗牌 $$$b$$$。

给定两个数组 $$$a$$$ 和 $$$b$$$。寻找一个可能的 幻数 $$$k$$$。不过,有很小的可能是Serval欺骗了你,这样的整数并不存在。在这种情况下,输出$$$-1$$$。

可以证明,在问题的约束下,如果存在这样一个整数$$$k$$$,则存在不超过$$$10^9$$$的有效答案。并且您需要保证输出中有 $$$k\le 10^9$$$ 。

$$$^{\text{*}}$$$$$$a_i \bmod k$$$ 表示 $$$a_i$$$ 除以 $$$k$$$ 所得的余数。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 10^4$$$) — 数组 $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0\leq a_i\leq 10^6$$$) — 数组 $$$a$$$ 的元素。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$0\leq b_i\leq 10^6$$$) — 数组 $$$b$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^4$$$。

输出

对于每个测试用例,输出一个整数 $$$k$$$ ($$$1\leq k\leq 10^9$$$) — 幻数 你发现了。如果无法找到这样的整数,则打印 $$$-1$$$。

如果有多个答案,您可以打印其中任何一个。

示例

输入
复制

5
4
3 5 2 7
0 1 1 1
5
3 1 5 2 4
1 2 3 4 5
6
2 3 4 7 8 9
1 2 3 6 7 8
5
21 22 25 28 20
0 1 2 1 0
6
1 1 2 3 5 8
0 0 1 1 0 0

输出
复制

2
31415926
-1
4
-1

注意

在第一个测试用例中,如果$$$k\ge 3$$$,那么$$$2=a_3\bmod k$$$应该在数组$$$b$$$中,这导致了矛盾。对于$$$k = 1$$$,$$$[a_1\bmod k, a_2\bmod k, a_3\bmod k, a_4 \bmod k] = [0,0,0,0]$$$,不能被打乱到$$$b$$$。对于$$$k = 2$$$,$$$[a_1\bmod k, a_2\bmod k, a_3\bmod k, a_4 \bmod k] = [1,1,0,1]$$$,可以将其打乱为$$$b$$$。因此,唯一可能的答案是$$$k=2$$$。

在第二个测试用例中,请注意 $$$b$$$ 可以通过对 $$$a$$$ 进行混洗来获得。因此,$$$6$$$ 和 $$$10^9$$$ 之间的所有整数都是可能的答案。

在第三个测试用例中,可以证明这样的$$$k$$$不存在。被薮猫骗了!