CF1780B GCD Partition

在 Kira 的家中，Josuke 看到桌子上有一张写着任务的纸条。 任务内容如下。有一个长度为 $n$ 的数组 $a$。对这个数组进行如下操作： - 选择一个整数 $k > 1$； - 将数组分成 $k$ 个子段$^\dagger$； - 计算每个子段的和，并将这些和写入另一个数组 $b$（其中子段 $(l, r)$ 的和为 ${\sum_{j = l}^{r}a_j}$）； - 这种划分的最终得分为 $\gcd(b_1, b_2, \ldots, b_k)^\ddagger$。 你的任务是找到一种划分方式，使得得分最大。Josuke 对这个任务很感兴趣，但他不擅长计算机科学。请你帮他找到最大可能的得分。 $^\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）](https://en.wikipedia.org/wiki/Greatest_common_divisor)。

第一行包含一个整数 $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$。

对于每个测试用例，输出一个整数，表示最优划分下的最大得分。

在第一个测试用例中，你可以选择 $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$。 由 ChatGPT 4.1 翻译