codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1780B.md (2426B)


      1 Source: https://codeforces.com/problemset/problem/1780/B
      2 
      3 B. GCD Partition
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 While at Kira's house, Josuke saw a piece of paper on the table with a task written on it.
     22 
     23 The task sounded as follows. There is an array $a$ of length $n$. On this array, do the following:
     24 
     25 * select an integer $k \gt 1$;
     26 * split the array into $k$ subsegments $^\dagger$;
     27 * 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}$);
     28 * the final score of such a split will be $\gcd(b_1, b_2, \ldots, b_k)^\ddagger$.
     29 
     30 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.
     31 
     32 $^\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.
     33 
     34 $^\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$.
     35 
     36 Input
     37 
     38 The first line contains a single number $t$ ($1 \le t \le 10^4$) — the number of test cases.
     39 
     40 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$.
     41 
     42 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.
     43 
     44 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     45 
     46 Output
     47 
     48 For each test case print a single integer — the maximum score for the optimal partition.
     49 
     50 Example
     51 
     52 Input
     53 
     54 ```
     55 6
     56 
     57 4
     58 
     59 2 2 1 3
     60 
     61 2
     62 
     63 1 2
     64 
     65 3
     66 
     67 1 4 5
     68 
     69 6
     70 
     71 1 2 1 1 1 3
     72 
     73 10
     74 
     75 12 30 37 88 12 78 89 17 2 12
     76 
     77 6
     78 
     79 7 7 7 7 7 7
     80 ```
     81 
     82 Output
     83 
     84 ```
     85 4
     86 1
     87 5
     88 3
     89 1
     90 21
     91 ```
     92 
     93 Note
     94 
     95 In the first test case, you can choose $k = 2$ and split the array into subsegments $(1, 2)$ and $(3, 4)$.
     96 
     97 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$.
     98 
     99 In the fourth test case, you can choose $k = 3$ and split the array into subsegments $(1, 2), (3, 5), (6, 6)$.
    100 
    101 The split score is $\gcd(1 + 2, 1 + 1 + 1, 3) = 3$.