← 返回题目列表

Codeforces · 1780/B

B. GCD 分区

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

在基拉家的时候,仗助看到桌子上有一张纸,上面写着任务。

任务听起来如下。有一个长度为$$$n$$$的数组$$$a$$$。在此阵列上,执行以下操作:

- 选择一个整数$$$k > 1$$$;
- 将数组分割为$$$k$$$子段$$$^\dagger$$$;
- 计算每个$$$k$$$子段的总和并将这些总和写入另一个数组$$$b$$$(其中子段$$$(l, r)$$$的总和为$$${\sum_{j = l}^{r}a_j}$$$);
- 这种分割的最终分数将为 $$$\gcd(b_1, b_2, \ldots, b_k)^\ddagger$$$。

任务是找到得分最大的分区。仗助对这项任务很感兴趣,但计算机科学并不强。帮助他找到尽可能高的分数。

$$$^\dagger$$$ 将数组划分为 $$$k$$$ 子段是 $$$k$$$ 数字对 $$$(l_1, r_1), (l_2, r_2), \ldots, (l_k, r_k)$$$ 使得 $$$l_i \le r_i$$$ 并且对于每个 $$$1 \le j \le k - 1$$$ $$$l_{j + 1} = r_j + 1$$$,还有 $$$l_1 = 1$$$ 和 $$$r_k = n$$$。这些对代表子段。

$$$^\ddagger$$$ $$$\gcd(b_1, b_2, \ldots, b_k)$$$ 代表数组 $$$b$$$ 的最大公约数 (GCD)。

输入

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

对于每个测试用例,第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, a_3, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9 $$$) — 数组 $$$a$$$ 本身。

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

输出

对于每个测试用例,打印一个整数 - 最佳分区的最大分数。

示例

输入 #1

6
4
2 2 1 3
2
1 2
3
1 4 5
6
1 2 1 1 1 3
10
12 30 37 88 12 78 89 17 2 12
6
7 7 7 7 7 7

输出 #1

4
1
5
3
1
21

注意

在第一个测试用例中,您可以选择 $$$k = 2$$$ 并将数组拆分为子段 $$$(1, 2)$$$ 和 $$$(3, 4)$$$。

那么这样一个分区的分数将等于 $$$\gcd(a_1 + a_2, a_3 + a_4) = \gcd(2 + 2, 1 + 3) = \gcd(4, 4) = 4$$$。

在第四个测试用例中,您可以选择 $$$k = 3$$$ 并将数组拆分为子段 $$$(1, 2), (3, 5), (6, 6)$$$。

分割得分为 $$$\gcd(1 + 2, 1 + 1 + 1, 3) = 3$$$。