CF1780B.GCD Partition
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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 † ;
- 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 ∑j=lraj );
- the final score of such a split will be gcd(b1,b2,…,bk)‡ .
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.
† A division of an array into k subsegments is k pairs of numbers (l1,r1),(l2,r2),…,(lk,rk) such that li≤ri and for every 1≤j≤k−1 lj+1=rj+1 , also l1=1 and rk=n . These pairs represent the subsegments.
‡ gcd(b1,b2,…,bk) stands for the greatest common divisor (GCD) of the array b .
输入格式
The first line contains a single number t ( 1≤t≤104 ) — the number of test cases.
For each test case, the first line contains one integer n ( 2≤n≤2⋅105 ) — the length of the array a .
The second line contains n integers a1,a2,a3,…,an ( $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⋅105 .
输出格式
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(a1+a2,a3+a4)=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 .