喵哈喽~！各位看官，今天由我，小猫娘，来为大家讲解这道有趣的题目哦！这道题叫做「250 Thousand Tons of TNT」，听起来就很厉害的样子，对吧？不过别担心，只要跟着本喵的思路走，再难的题目也会变得像撸猫一样简单的说！

题目大意

简单来说呢，就是有一个叫 Alex 的人，他有 n 个箱子排成一排，每个箱子都有自己的重量 a_i 嘛。他想用很多辆卡车把这些箱子运走。

所有的卡车都一样大，每辆车都得装 k 个箱子。装箱的规则是：

• 第一辆车装前 k 个箱子。
• 第二辆车装接下来 k 个箱子。
• ...以此类推，直到所有箱子都被装完。

这就要求 n 必须能被 k 整除才行哦！

Alex 这个人呢，有点小坏心眼，他希望所有卡车里，装得最重的和装得最轻的，它们之间的重量差越大越好！他可以自由选择 k 的值（只要 k 能整除 n），所以我们的任务就是帮他找到一个 k，让这个最大的重量差变得最大，然后把这个差值告诉他。

如果只有一个卡车（也就是 k=n），那差值就是 0 啦~ 听明白了吗喵？

题解方法

这道题的核心就是要找到一个最合适的 k 值嘛。那我们该怎么找呢？

首先，我们得明白 k 必须满足什么条件。因为每辆车都要装 k 个箱子，而且所有 n 个箱子都要被装完，所以 n 必须能被 k 整除。也就是说，k 必须是 n 的一个因子（或者叫约数）的说。

所以呀，我们的问题就变成了：遍历所有 n 的因子 k（除了 k=n 本身，因为 k=n 时只有一个卡车，差值是 0），对于每个 k，计算出对应的最大重量差，然后在所有这些差值里找一个最大的！

那么，具体要怎么做呢喵？

1. 找到所有因子：一个一个试太慢啦！我们可以用一个聪明的方法：从 1 遍历到 sqrt(n)。如果 i 是 n 的因子，那么 n/i 也一定是 n 的因子。这样我们一次就能找到一对因子，效率高多啦！

2. 快速计算每辆卡车的总重量：对于一个确定的 k，我们需要计算 n/k 辆卡车的重量。第一辆是 a_1 到 a_k 的和，第二辆是 a_{k+1} 到 a_{2k} 的和…… 如果每次都重新加一遍，会很慢的。这时候，我们的好朋友「前缀和」就登场啦！

   • 我们可以先预处理一个前缀和数组 prefix_sum，其中 prefix_sum[i] 表示前 i 个箱子的总重量。
   • 这样，第 j 辆卡车（装的是从 (j-1)*k+1 到 j*k 的箱子）的重量就可以用 prefix_sum[j*k] - prefix_sum[(j-1)*k] 瞬间算出来！是不是很神奇喵？

3. 计算并更新答案：对于每个因子 k，我们用前缀和快速算出所有卡车的重量，然后找到其中的最大值 max_weight 和最小值 min_weight。它们的差 max_weight - min_weight 就是当前 k 对应的答案。我们用一个变量 max_abs_diff 来记录所有 k 算出来的差值中的最大值。

把所有因子都试一遍之后，max_abs_diff 就是我们最终的答案啦！

题解

这是本喵写的 C++ 代码，大家可以参考一下哦~

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <limits>

// 这是一个帮助我们计算特定k值下重量差的函数哦
long long calculate_diff(int n, int k, const std::vector<long long>& prefix_sum) {
    long long min_weight = std::numeric_limits<long long>::max(); // 先把最小重量设成一个超大的数
    long long max_weight = std::numeric_limits<long long>::min(); // 最大重量设成一个超小的数
    
    // 遍历每一辆卡车~
    for (int i = 1; i <= n / k; ++i) {
        // 用前缀和快速算出第i辆卡车的重量！
        long long current_weight = prefix_sum[i * k] - prefix_sum[(i - 1) * k];
        min_weight = std::min(min_weight, current_weight); // 更新最小重量
        max_weight = std::max(max_weight, current_weight); // 更新最大重量
    }
    
    return max_weight - min_weight; // 返回最大和最小的差值
}

void solve() {
    int n;
    std::cin >> n;
    std::vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 预处理前缀和数组，喵~
    // prefix_sum[i] 表示前 i 个箱子的总重量
    std::vector<long long> prefix_sum(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefix_sum[i + 1] = prefix_sum[i] + a[i];
    }
    
    long long max_abs_diff = 0; // 用来记录最终答案的变量
    
    // 遍历 n 的所有因子 k
    // 我们只用遍历到 sqrt(n) 就好啦，因为如果 i 是因子，n/i 也是因子
    for (int k = 1; k * k <= n; ++k) {
        if (n % k == 0) { // 找到了一个因子 k！
            // 处理因子 k
            if (k < n) { // k=n 的情况只有一个卡车，差值是0，不用管
                max_abs_diff = std::max(max_abs_diff, calculate_diff(n, k, prefix_sum));
            }
            
            // 处理另一个因子 n/k
            int other_k = n / k;
            if (other_k != k && other_k < n) { // 同样，k=n的情况不用管，也要避免和k重复计算
                max_abs_diff = std::max(max_abs_diff, calculate_diff(n, other_k, prefix_sum));
            }
        }
    }
    
    std::cout << max_abs_diff << "\n";
}

int main() {
    // 加速输入输出，让程序跑得更快一点~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

知识点介绍

为了让大家更好地理解这个解法，本喵来给大家科普一下里面用到的两个小技巧吧！

1. 前缀和 (Prefix Sums) 喵~

前缀和是一种非常实用的小技巧，用来快速计算一个序列（比如我们的箱子重量数组）中任意一段区间的和。它的思想很简单：

• 是什么： 创建一个新数组，我们叫它 prefix_sum。prefix_sum[i] 存储的是原数组从第 0 个元素到第 i-1 个元素的总和。
• 怎么算： prefix_sum[0] = 0，然后 prefix_sum[i] = prefix_sum[i-1] + a[i-1]。递推一下就好啦！
• 怎么用： 想要计算原数组中从下标 L 到 R（包含 L 和 R）这一段的和，只需要用 prefix_sum[R+1] - prefix_sum[L] 就可以了！比如我们这道题里，第 i 辆卡车（1-indexed）装的是 (i-1)*k 到 i*k-1 的箱子，它的重量就是 prefix_sum[i*k] - prefix_sum[(i-1)*k]。是不是超级方便的说！

2. 高效找因子 (Finding Divisors Efficiently) 嘛

当我们要找一个数 n 的所有因子时，最笨的办法是从 1 遍历到 n，看谁能整除 n。但如果 n 很大，这就太慢了。

一个更聪明的办法是只遍历到 sqrt(n)（n 的平方根）。

• 为什么可以： 因为因子总是成对出现的！如果 i 是 n 的一个因子，那么 n/i 也必然是 n 的一个因子。举个例子，对于 n=12，2 是它的因子，那么 12/2 = 6 也是因子。3 是因子，12/3 = 4 也是因子。
• 怎么做： 我们从 i = 1 循环到 i * i <= n。在循环里，如果 i 能整除 n（即 n % i == 0），我们就找到了一个因子 i。同时，我们也找到了它的搭档 n/i！这样一来，我们只需要检查 sqrt(n) 那么多次，就能找到所有的因子了，速度快了很多很多哦！
  • 注意：如果 n 是一个完全平方数，比如 36，当 i=6 时，n/i 也是 6，这时候它们是同一个因子，不要重复计算就好啦。

好啦，今天的讲解就到这里啦~ 是不是很简单呢？只要把问题分解开，找到合适的工具（比如前缀和和找因子的技巧），问题就迎刃而解了！希望本喵的讲解对大家有帮助哦！下次再见啦，喵~