← 返回题目列表

Codeforces · 2167/D

D. 又一个数组问题

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

给定一个整数 $$$n$$$ 和一个长度为 $$$n$$$ 的数组 $$$a$$$。

找到 最小 整数 $$$x$$$ ($$$2 \le x \le 10^{18}$$$) 使得存在索引 $$$i$$$ ($$$1 \le i \le n$$$) $$$\gcd$$$$$$^{\text{*}}$$$$$$(a_i, x) = 1$$$。如果$$$[2,10^{18}]$$$范围内不存在这样的$$$x$$$,则输出$$$-1$$$。

$$$^{\text{*}}$$$$$$\gcd(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

以下 $$$t$$$ 测试用例均由两行组成:

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^{5}$$$) — 数组的长度。

第二行包含 $$$n$$$ 空格分隔的整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{18}$$$)。

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

输出

对于每个测试用例,输出一个整数:最小的 $$$x$$$ ($$$2 \le x \le 10^{18}$$$) 使得存在索引 $$$i$$$ 且 $$$\gcd(a_i, x) = 1$$$。如果$$$[2,10^{18}]$$$范围内不存在这样的$$$x$$$,则打印$$$-1$$$。

示例

输入
复制

4
1
1
4
6 6 12 12
3
24 120 210
4
2 4 6 10

输出
复制

2
5
5
3

注意

在第一个测试用例中,$$$\gcd(2,1)=1$$$,这是满足条件的最小数字。

在第二个测试用例中:

  • $$$\gcd(2,6)=2$$$, $$$\gcd(2,12)=2$$$,所以 $$$2$$$ 不可能是答案。
  • $$$\gcd(3,6)=3$$$, $$$\gcd(3,12)=3$$$,所以 $$$3$$$ 不可能是答案。
  • $$$\gcd(4,6)=2$$$, $$$\gcd(4,12)=4$$$,所以 $$$4$$$ 不可能是答案。
  • $$$\gcd(5,6)=1$$$,所以答案是$$$5$$$。

在第三个测试用例中:

  • $$$\gcd(2,24)=2$$$, $$$\gcd(2,120)=2$$$, $$$\gcd(2,210)=2$$$,所以 $$$2$$$ 不可能是答案。
  • $$$\gcd(3,24)=3$$$, $$$\gcd(3,120)=3$$$, $$$\gcd(3,210)=3$$$,所以 $$$3$$$ 不可能是答案。
  • $$$\gcd(4,24)=4$$$, $$$\gcd(4,120)=4$$$, $$$\gcd(4,210)=2$$$,所以 $$$4$$$ 不可能是答案。
  • $$$\gcd(5,24)=1$$$,所以答案是$$$5$$$。

在第四个测试用例中:

  • $$$\gcd(2,2)=2$$$、$$$\gcd(2,4)=2$$$、$$$\gcd(2,6)=2$$$、$$$\gcd(2,10)=2$$$,所以 $$$2$$$ 不可能是答案。
  • $$$\gcd(3,2)=1$$$,所以答案是$$$3$$$。