← 返回题目列表

Codeforces · 2124/C

C. 子集乘法

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

Alice 有一个数组 $$$a$$$,由 $$$n$$$ 正整数组成。该数组满足 $$$a_i$$$ 除以 $$$a_{i+1}$$$ 对于每个 $$$1 \leq i \leq n - 1$$$ 的美丽属性。

鲍勃看到爱丽丝美丽的阵列,很嫉妒。为了破坏她,Bob 首先创建一个大小为 $$$n$$$ 的数组 $$$b$$$,使得每个 $$$1 \leq i \leq n$$$ 都有 $$$b_i=a_i$$$。然后,他选择一个正整数 $$$x$$$ 并将 $$$b$$$ 中的一些(可能没有,也可能全部)元素乘以 $$$x$$$。

正式地,他选择一个(可能为空)子集 $$$S\subseteq\{1,2,\ldots,n\}$$$,并且对于 S$$$ 中的每个 $$$i\,他设置 $$$b_i:=b_i\cdot x$$$。

给定一个数组 $$$b$$$,但你不知道数组 $$$a$$$ 和所选数字 $$$x$$$。请输出 Bob 可以选择的任何整数 $$$x$$$,以便将正确数组 $$$a$$$ 的某些元素子集乘以 $$$x$$$ 将得到数组 $$$b$$$。保证答案存在。如果有多个可能的整数,则可以输出其中任何一个。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 6\cdot10^5$$$) — 数组 $$$b$$$ 的长度。

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

这是 保证 数组 $$$b$$$ 可以从一些漂亮的数组 $$$a$$$ 和一些正整数 $$$x$$$ 中获得,如语句中所述。

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

输出

对于每个测试用例,在新行上输出 $$$x$$$ ($$$1 \leq x \leq 10^9$$$) 的任何可能值。保证 $$$x$$$ 至少存在一个值。

示例

输入
复制

4
2
2 4
3
1 1000000000 500000000
4
4 8 4 8
7
42 42 14 84 28 73080 255780

输出
复制

343
2
4
6

注意

在第一个测试用例中,Bob 可能选择 $$$x=343$$$ 和 $$$S=\{\}$$$ (意味着他根本没有更改数组 $$$a$$$)。

在第三个测试用例中,Bob 可能选择 $$$x=4$$$ 和 $$$S=\{1,2\}$$$,这意味着他将 $$$b_1$$$ 和 $$$b_2$$$ 都乘以 $$$4$$$。原数组为$$$\{1,2,4,8\}$$$,满足要求的属性。