310082: CF1780B. GCD Partition
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
GCD Partition
题意翻译
### 简要题意 给定长度为 $n$ 的数组 $a$。 要求把它分成 $k(1\lt k\le n)$ 个子段，要求**所有子段和的[最大公约数](https://baike.baidu.com/item/%E6%9C%80%E5%A4%A7%E5%85%AC%E7%BA%A6%E6%95%B0/869308)最大**，求这个最大值。 设 $l_i,r_i(1\le l_i \le k)$ 分表示第 $i$ 个子段的左右端点。这个子段的子段和 $b_i=\sum\limits_{j=l_i}^{r_i}a_j$。 要求 $l_i\le r_i$，对于所有 $1\le j\lt k$，有 $l_{j+1}=r_j+1$，并且 $l_1=1,r_k=n$。**最大化** $\gcd(b_1,b_2,...,b_k)$。 ### 输入 第一行一个整数 $t(1\le t \le 10^4)$ 表示数据组数。 对于每组数据： 第一行一个整数 $n(2\le n\le 2\times 10^5)$ 表示数组 $a$ 长度。 第二行 $n$ 个整数 $a_1,a_2,a_3,...,a_n(1\le a_i\le10^9)$ 表示数组 $a$。 另外保证 $\sum n\le 2\times 10^5$。 ### 输出 对于每组数据，一行一个最大值，具体见题意部分。 ### 说明/提示 对于第一组数据，分为两个 $(k=2)$ 子段 $(1,2),(3,4)$，最大公约数最大值为 $4$。题目描述
While at Kira's house, Josuke saw a piece of paper on the table with a task written on it. The task sounded as follows. There is an array $ a $ of length $ n $ . On this array, do the following: - select an integer $ k > 1 $ ; - split the array into $ k $ subsegments $ ^\dagger $ ; - calculate the sum in each of $ k $ subsegments and write these sums to another array $ b $ (where the sum of the subsegment $ (l, r) $ is $ {\sum_{j = l}^{r}a_j} $ ); - the final score of such a split will be $ \gcd(b_1, b_2, \ldots, b_k)^\ddagger $ . The task is to find such a partition that the score is maximum possible. Josuke is interested in this task but is not strong in computer science. Help him to find the maximum possible score. $ ^\dagger $ A division of an array into $ k $ subsegments is $ k $ pairs of numbers $ (l_1, r_1), (l_2, r_2), \ldots, (l_k, r_k) $ such that $ l_i \le r_i $ and for every $ 1 \le j \le k - 1 $ $ l_{j + 1} = r_j + 1 $ , also $ l_1 = 1 $ and $ r_k = n $ . These pairs represent the subsegments. $ ^\ddagger $ $ \gcd(b_1, b_2, \ldots, b_k) $ stands for the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of the array $ b $ .输入输出格式
输入格式
The first line contains a single number $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. For each test case, the first line contains one integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ) — the length of the array $ a $ . The second line contains $ n $ integers $ a_1, a_2, a_3, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the array $ a $ itself. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .
输出格式
For each test case print a single integer — the maximum score for the optimal partition.
输入输出样例
输入样例 #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说明
In the first test case, you can choose $ k = 2 $ and split the array into subsegments $ (1, 2) $ and $ (3, 4) $ . Then the score of such a partition will be equal to $ \gcd(a_1 + a_2, a_3 + a_4) = \gcd(2 + 2, 1 + 3) = \gcd(4, 4) = 4 $ . In the fourth test case, you can choose $ k = 3 $ and split the array into subsegments $ (1, 2), (3, 5), (6, 6) $ . The split score is $ \gcd(1 + 2, 1 + 1 + 1, 3) = 3 $ .Input
题意翻译
### 简要题意 给定长度为 $n$ 的数组 $a$。 要求把它分成 $k(1\lt k\le n)$ 个子段，要求**所有子段和的[最大公约数](https://baike.baidu.com/item/%E6%9C%80%E5%A4%A7%E5%85%AC%E7%BA%A6%E6%95%B0/869308)最大**，求这个最大值。 设 $l_i,r_i(1\le l_i \le k)$ 分表示第 $i$ 个子段的左右端点。这个子段的子段和 $b_i=\sum\limits_{j=l_i}^{r_i}a_j$。 要求 $l_i\le r_i$，对于所有 $1\le j\lt k$，有 $l_{j+1}=r_j+1$，并且 $l_1=1,r_k=n$。**最大化** $\gcd(b_1,b_2,...,b_k)$。 ### 输入 第一行一个整数 $t(1\le t \le 10^4)$ 表示数据组数。 对于每组数据： 第一行一个整数 $n(2\le n\le 2\times 10^5)$ 表示数组 $a$ 长度。 第二行 $n$ 个整数 $a_1,a_2,a_3,...,a_n(1\le a_i\le10^9)$ 表示数组 $a$。 另外保证 $\sum n\le 2\times 10^5$。 ### 输出 对于每组数据，一行一个最大值，具体见题意部分。 ### 说明/提示 对于第一组数据，分为两个 $(k=2)$ 子段 $(1,2),(3,4)$，最大公约数最大值为 $4$。Output
**题目大意：**
给定一个长度为 $ n $ 的数组 $ a $，要将这个数组分成 $ k $ 个子段（$ 1 < k \le n $），使得所有子段和的最大公约数尽可能大。要求从左到右依次划分，不能有交叉或遗漏，即对于所有 $ 1 \le j < k $，第 $ j+1 $ 个子段的起始点 $ l_{j+1} $ 等于第 $ j $ 个子段的结束点 $ r_j $ 加 1，并且第一个子段从第一个元素开始，最后一个子段以最后一个元素结束。求这个最大公约数的最大值。
**输入数据格式：**
第一行一个整数 $ t (1 \le t \le 10^4) $ 表示数据组数。
每组数据包括两行：
第一行一个整数 $ n (2 \le n \le 2 \times 10^5) $ 表示数组 $ a $ 的长度。
第二行 $ n $ 个整数 $ a_1, a_2, a_3, \ldots, a_n (1 \le a_i \le 10^9) $ 表示数组 $ a $ 的元素。
保证所有组数据中 $ n $ 的总和不超过 $ 2 \times 10^5 $。
**输出数据格式：**
对于每组数据，输出一行一个整数，表示最大公约数的最大值。
**说明/提示：**
例如，对于第一组数据，当分为两个子段（$ k=2 $）$ (1,2) $ 和 $ (3,4) $ 时，最大公约数的最大值为 $ 4 $。**题目大意：** 给定一个长度为 $ n $ 的数组 $ a $，要将这个数组分成 $ k $ 个子段（$ 1 < k \le n $），使得所有子段和的最大公约数尽可能大。要求从左到右依次划分，不能有交叉或遗漏，即对于所有 $ 1 \le j < k $，第 $ j+1 $ 个子段的起始点 $ l_{j+1} $ 等于第 $ j $ 个子段的结束点 $ r_j $ 加 1，并且第一个子段从第一个元素开始，最后一个子段以最后一个元素结束。求这个最大公约数的最大值。 **输入数据格式：** 第一行一个整数 $ t (1 \le t \le 10^4) $ 表示数据组数。 每组数据包括两行： 第一行一个整数 $ n (2 \le n \le 2 \times 10^5) $ 表示数组 $ a $ 的长度。 第二行 $ n $ 个整数 $ a_1, a_2, a_3, \ldots, a_n (1 \le a_i \le 10^9) $ 表示数组 $ a $ 的元素。 保证所有组数据中 $ n $ 的总和不超过 $ 2 \times 10^5 $。 **输出数据格式：** 对于每组数据，输出一行一个整数，表示最大公约数的最大值。 **说明/提示：** 例如，对于第一组数据，当分为两个子段（$ k=2 $）$ (1,2) $ 和 $ (3,4) $ 时，最大公约数的最大值为 $ 4 $。
给定一个长度为 $ n $ 的数组 $ a $，要将这个数组分成 $ k $ 个子段（$ 1 < k \le n $），使得所有子段和的最大公约数尽可能大。要求从左到右依次划分，不能有交叉或遗漏，即对于所有 $ 1 \le j < k $，第 $ j+1 $ 个子段的起始点 $ l_{j+1} $ 等于第 $ j $ 个子段的结束点 $ r_j $ 加 1，并且第一个子段从第一个元素开始，最后一个子段以最后一个元素结束。求这个最大公约数的最大值。
**输入数据格式：**
第一行一个整数 $ t (1 \le t \le 10^4) $ 表示数据组数。
每组数据包括两行：
第一行一个整数 $ n (2 \le n \le 2 \times 10^5) $ 表示数组 $ a $ 的长度。
第二行 $ n $ 个整数 $ a_1, a_2, a_3, \ldots, a_n (1 \le a_i \le 10^9) $ 表示数组 $ a $ 的元素。
保证所有组数据中 $ n $ 的总和不超过 $ 2 \times 10^5 $。
**输出数据格式：**
对于每组数据，输出一行一个整数，表示最大公约数的最大值。
**说明/提示：**
例如，对于第一组数据，当分为两个子段（$ k=2 $）$ (1,2) $ 和 $ (3,4) $ 时，最大公约数的最大值为 $ 4 $。**题目大意：** 给定一个长度为 $ n $ 的数组 $ a $，要将这个数组分成 $ k $ 个子段（$ 1 < k \le n $），使得所有子段和的最大公约数尽可能大。要求从左到右依次划分，不能有交叉或遗漏，即对于所有 $ 1 \le j < k $，第 $ j+1 $ 个子段的起始点 $ l_{j+1} $ 等于第 $ j $ 个子段的结束点 $ r_j $ 加 1，并且第一个子段从第一个元素开始，最后一个子段以最后一个元素结束。求这个最大公约数的最大值。 **输入数据格式：** 第一行一个整数 $ t (1 \le t \le 10^4) $ 表示数据组数。 每组数据包括两行： 第一行一个整数 $ n (2 \le n \le 2 \times 10^5) $ 表示数组 $ a $ 的长度。 第二行 $ n $ 个整数 $ a_1, a_2, a_3, \ldots, a_n (1 \le a_i \le 10^9) $ 表示数组 $ a $ 的元素。 保证所有组数据中 $ n $ 的总和不超过 $ 2 \times 10^5 $。 **输出数据格式：** 对于每组数据，输出一行一个整数，表示最大公约数的最大值。 **说明/提示：** 例如，对于第一组数据，当分为两个子段（$ k=2 $）$ (1,2) $ 和 $ (3,4) $ 时，最大公约数的最大值为 $ 4 $。