← 返回题目列表

Codeforces · 1899/B

B. 25万吨TNT

中文机器翻译题面 查看原题

Alex正在参加BrMeast另一个视频的拍摄,BrMeast让Alex准备25万吨TNT,但Alex听不太清,就准备了$$$n$$$个箱子,排成一排等待卡车。左边第 $$$i$$$ 个盒子重 $$$a_i$$$ 吨。

Alex 将使用的所有卡车都装有相同数量的箱子,用 $$$k$$$ 表示。加载按以下方式进行:

- 第一个 $$$k$$$ 盒子被送到第一辆卡车,
- 第二个 $$$k$$$ 箱子被运往第二辆卡车,
- $$$\dotsb$$$
- 最后 $$$k$$$ 箱子被送到第 $$$\frac{n}{k}$$$ 卡车。

装载完成后,每辆卡车必须恰好装有 $$$k$$$ 个箱子。换句话说,如果在某个时刻不可能将 $$$k$$$ 箱子准确地装载到卡车上,那么使用该 $$$k$$$ 的装载选项是不可能的。

Alex 讨厌正义,因此他希望两辆卡车的总重量之间的最大绝对差值尽可能大。如果只有一辆卡车,则该值为 $$$0$$$。

Alex 有相当多的人脉,因此对于每 $$$1 \leq k \leq n$$$,他可以找到一家公司,使其每辆卡车都能恰好容纳 $$$k$$$ 箱子。打印任意两辆卡车总重量之间的最大绝对差。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 150\,000$$$) — 盒子的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 盒子的权重。

保证所有测试用例的$$$n$$$总和不超过$$$150\,000$$$。

输出

对于每个测试用例,打印一个整数 - 问题的答案。

示例

输入 #1

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

1
9
0
189114
112141

注意

在第一种情况下,我们应该选择两辆卡车,因此第一辆卡车只有第一个箱子,第二辆卡车只有第二个箱子。

在第二种情况下,我们应该选择六辆卡车,因此最大值为 $$$10$$$,最小值为 $$$1$$$,答案为 $$$10 - 1 = 9$$$。

在第三种情况下,对于任何可能的$$$k$$$,卡车将具有相同的箱子总重量,因此答案是$$$0$$$。