CF1899B 250 Thousand Tons of TNT

Alex 正在参与 BrMeast 的又一次视频拍摄，BrMeast 让 Alex 准备 25 万吨 TNT，但 Alex 没听清楚，于是他准备了 $n$ 个箱子，并将它们排成一排等待卡车。第 $i$ 个从左数的箱子重量为 $a_i$ 吨。 所有 Alex 要用的卡车每辆都能装下相同数量的箱子，记为 $k$。装载过程如下： - 前 $k$ 个箱子装进第一辆卡车， - 接下来的 $k$ 个箱子装进第二辆卡车， - 以此类推， - 最后 $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$。

对于每个测试用例，输出一个整数，表示题目的答案。

在第一个样例中，我们应选择两辆卡车，第一辆只装第一个箱子，第二辆只装第二个箱子。 在第二个样例中，应选择六辆卡车，最大值为 $10$，最小值为 $1$，答案为 $10 - 1 = 9$。 在第三个样例中，无论选择哪种 $k$，每辆卡车装箱子的总重量都相同，所以答案为 $0$。 由 ChatGPT 4.1 翻译