310848: CF1899B. 250 Thousand Tons of TNT
Description
Alex is participating in the filming of another video of BrMeast, and BrMeast asked Alex to prepare 250 thousand tons of TNT, but Alex didn't hear him well, so he prepared $n$ boxes and arranged them in a row waiting for trucks. The $i$-th box from the left weighs $a_i$ tons.
All trucks that Alex is going to use hold the same number of boxes, denoted by $k$. Loading happens the following way:
- The first $k$ boxes goes to the first truck,
- The second $k$ boxes goes to the second truck,
- $\dotsb$
- The last $k$ boxes goes to the $\frac{n}{k}$-th truck.
Upon loading is completed, each truck must have exactly $k$ boxes. In other words, if at some point it is not possible to load exactly $k$ boxes into the truck, then the loading option with that $k$ is not possible.
Alex hates justice, so he wants the maximum absolute difference between the total weights of two trucks to be as great as possible. If there is only one truck, this value is $0$.
Alex has quite a lot of connections, so for every $1 \leq k \leq n$, he can find a company such that each of its trucks can hold exactly $k$ boxes. Print the maximum absolute difference between the total weights of any two trucks.
InputThe first line contains one integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
The first line of each test case contains one integer $n$ ($1 \leq n \leq 150\,000$) — the number of boxes.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^9$) — the weights of the boxes.
It is guaranteed that the sum of $n$ for all test cases does not exceed $150\,000$.
OutputFor each test case, print a single integer — the answer to the problem.
ExampleInput5 2 1 2 6 10 2 3 6 1 3 4 1000000000 1000000000 1000000000 1000000000 15 60978 82265 78961 56708 39846 31071 4913 4769 29092 91348 64119 72421 98405 222 14294 8 19957 69913 37531 96991 57838 21008 14207 19198Output
1 9 0 189114 112141Note
In the first case, we should pick two trucks, so the first one will have only the first box, and the second one will have only the second box.
In the second case, we should pick six trucks, so the maximum will be $10$, the minimum will be $1$, and the answer is $10 - 1 = 9$.
In the third case, for any possible $k$, the trucks will have the same total weight of boxes, so the answer is $0$.
Output
这个题目是关于将一系列箱子装上卡车的问题。有n个箱子，每个箱子的重量为a_i吨。所有卡车装载数量相同的箱子，记为k。装载过程如下：
- 前k个箱子装上第一辆卡车，
- 接下来的k个箱子装上第二辆卡车，
- 依此类推，
- 最后的k个箱子装上第n/k辆卡车。
完成装载后，每辆卡车必须有恰好k个箱子。如果某个时候无法将恰好k个箱子装上卡车，则该装载方案不可行。
要求输出的是任意两辆卡车总重量的最大绝对差值。如果只有一辆卡车，这个值为0。
输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。
- 每个测试用例的第一行包含一个整数n（1≤n≤150000），表示箱子的数量。
- 第二行包含n个整数a_1, a_2, ..., a_n（1≤a_i≤10^9），表示箱子的重量。
输出：
- 对于每个测试用例，输出一个整数，表示问题的答案。
示例：
输入：
```
5
2
1 2
6
10 2 3 6 1 3
4
1000000000 1000000000 1000000000 1000000000
15
60978 82265 78961 56708 39846 31071 4913 4769 29092 91348 64119 72421 98405 222 14294
8
19957 69913 37531 96991 57838 21008 14207 19198
```
输出：
```
1
9
0
189114
112141
```题目大意： 这个题目是关于将一系列箱子装上卡车的问题。有n个箱子，每个箱子的重量为a_i吨。所有卡车装载数量相同的箱子，记为k。装载过程如下： - 前k个箱子装上第一辆卡车， - 接下来的k个箱子装上第二辆卡车， - 依此类推， - 最后的k个箱子装上第n/k辆卡车。 完成装载后，每辆卡车必须有恰好k个箱子。如果某个时候无法将恰好k个箱子装上卡车，则该装载方案不可行。 要求输出的是任意两辆卡车总重量的最大绝对差值。如果只有一辆卡车，这个值为0。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。 - 每个测试用例的第一行包含一个整数n（1≤n≤150000），表示箱子的数量。 - 第二行包含n个整数a_1, a_2, ..., a_n（1≤a_i≤10^9），表示箱子的重量。 输出： - 对于每个测试用例，输出一个整数，表示问题的答案。 示例： 输入： ``` 5 2 1 2 6 10 2 3 6 1 3 4 1000000000 1000000000 1000000000 1000000000 15 60978 82265 78961 56708 39846 31071 4913 4769 29092 91348 64119 72421 98405 222 14294 8 19957 69913 37531 96991 57838 21008 14207 19198 ``` 输出： ``` 1 9 0 189114 112141 ```