咨询：计算双重求和式∑∑a_i mod a_j是否存在亚O(n²)算法

好问题！这个双重模求和确实没法像乘积求和那样直接用平方公式简化，但我们可以通过拆解模运算的定义来找到远优于$O(n^2)$的算法。

首先，先回忆模运算的数学定义：对于整数$a_i$和非零$a_j$，$a_i \mod a_j = a_i - a_j \times \lfloor \frac{a_i}{a_j} \rfloor$（这里的向下取整是数学上的标准定义，负数情况也适用）。

把这个定义代入原求和式，我们可以把它拆成两个独立的求和部分：
$$
\sum_{i=1}^n \sum_{j=1}^n a_i \mod a_j = \sum_{i,j} a_i - \sum_{i,j} a_j \times \lfloor \frac{a_i}{a_j} \rfloor
$$

接下来我们分别处理这两部分：

第一部分：快速计算$\sum_{i,j} a_i$ #

这部分非常简单：每个$a_i$会被累加$n$次（因为$j$从1到n遍历），所以总和就是：
$$
n \times \sum_{i=1}^n a_i
$$
只需要遍历一次数组算出所有元素的和，再乘以$n$即可，时间复杂度$O(n)$。

第二部分：优化计算$\sum_{i,j} a_j \times \lfloor \frac{a_i}{a_j} \rfloor$ #

我们可以交换求和顺序，把式子改写为：
$$
\sum_{j=1}^n a_j \times \left( \sum_{i=1}^n \lfloor \frac{a_i}{a_j} \rfloor \right)
$$
现在问题转化为：对每个$a_j$，计算数组中所有元素除以$a_j$的向下取整值的总和，再乘以$a_j$，最后把所有结果加起来。

高效计算单元素的取整和 #

为了避免对每个$(i,j)$都计算一次取整（这就是$O(n^2)$的根源），我们可以先对数组排序，再用二分查找来批量计算：

1. 预处理：排序数组
   先把数组从小到大排序，得到$b_1 \leq b_2 \leq ... \leq b_n$。排序的时间是$O(n \log n)$。

2. 对每个$b_j$计算取整和
   对于每个$b_j$，我们需要计算$\sum_{i=1}^n \lfloor \frac{b_i}{b_j} \rfloor$。利用排序后的数组，我们可以枚举$k=1,2,...$，找到所有满足$k \times b_j \leq b_i < (k+1) \times b_j$的元素数量，然后累加$k \times 数量$：

   • 对于$k=1$，找到第一个$\geq b_j$的元素位置，到第一个$\geq 2b_j$的位置之间的元素数量，每个贡献1；
   • 对于$k=2$，找到第一个$\geq 2b_j$到第一个$\geq 3b_j$的元素数量，每个贡献2；
   • 以此类推，直到$k \times b_j > b_n$（数组最大元素）。
   • 注意：$b_i < b_j$的元素取整结果为0，不需要累加。

   因为数组是排序好的，我们可以用二分查找（比如类似lower_bound的逻辑）快速找到每个区间的边界，每次二分的时间是$O(\log n)$。

3. 重复元素优化（可选）
   如果数组中有大量重复元素，我们可以先统计每个数值的出现频率（用哈希表或数组），然后只对不同的数值计算取整和，再乘以该数值的出现次数，这样能进一步减少计算量。

时间复杂度分析 #

排序的时间是$O(n \log n)$。对于每个元素$b_j$，枚举$k$的次数是$\lfloor \frac{b_n}{b_j} \rfloor$，而所有元素的$\lfloor \frac{b_n}{b_j} \rfloor$之和是$O(n \log b_n)$（类似于调和级数的变形，递增的$b_j$会让这个和快速收敛）。加上每次二分的$O(\log n)$，总时间复杂度是$O(n \log n + n \log b_n)$，在绝大多数实际场景下都远优于$O(n^2)$。

特殊情况处理 #

• $a_j=0$：模0在数学上无定义，需要根据题目要求处理（比如跳过这些$j$，或者返回错误）。
• 负数元素：如果数组中有负数，要注意向下取整的定义（比如$\lfloor -3/2 \rfloor = -2$），但模运算的展开式依然成立，只需要确保计算取整时符合数学定义即可。

总结 #

通过拆解模运算的定义，我们把原问题转化为两个可高效计算的部分。整体算法的时间复杂度可以做到$O(n \log n)$，完全碾压暴力的$O(n^2)$解法，尤其适合大数组的情况。

内容的提问来源于stack exchange，提问作者Leox