题意
给定长度为 \(n\) 的正整数序列 \(a_i\)，计算 \(\sum\limits_{1\le i,j\le n} (a_i\operatorname{mod} a_j)\)。
\(1 \le n, a_i\le 10^6\)
思路
观察数据范围，发现算法大概率是 \(\mathcal{O}(n\log n)\) 的。
先对式子进行转化
\[\sum_{1\le i,j\le n} (a_i\operatorname{mod} a_j) = \sum_{1\le i,j\le n} (a_i - \lfloor a_i/a_j\rfloor\times a_j) = \sum_{1\le i,j\le n}a_i -\sum_{1\le i,j\le n} \lfloor a_i/a_j\rfloor\times a_j \]第一项很好处理，考虑如何处理第二项
考虑固定 \(a_i,a_j\) 其中一个，对另一个进行统计。
假如固定 \(a_i\) ，统计 \(a_j\)，可以用整除分块做到 \(\mathcal{O}(n^{1.5})\)
假如固定 \(a_j\)，统计 \(a_i\)，那么我们需要枚举 \(a_j\) 的倍数，如果每个 \(a_j\) 都很小的话，似乎无法保证复杂度。
根号分治？仍然是根号级别的算法，甚至常数远大于整除分块。
那么如何处理呢？
解法
发现若是固定 \(a_j\)，枚举其倍数，那么只有 \(a_j\) 较小时需要枚举的次数较多，所以考虑对相同的 \(a_j\) 进行记忆化。
这看似是一个没什么用的优化，但是实际上将算法优化到了 \(\mathcal{O}(n\log n)\)。
为什么捏？
因为总枚举次数是小于 \(\sum\limits_{i = 1}^n \frac ni\) 的，而调和级数是 \(\log\) 级别的，于是这里算法的复杂度便变成了 \(\mathcal{O}(n\log n)\)。
具体实现上可以对 \(a_i\) 开桶计数，\(cnt_i\) 即为 \(i\) 在 \(a_i\) 中的出现次数，那么每个 \(i\) 的贡献为 \(i\times cnt_i\times \sum\limits_{j=1}^n \frac{a_j}{i}\)。
代码
#include <bits/stdc++.h>
using namespace std;
int n, a[1000005], cnt[1000005], sum[1000005], max_a;
long long ans;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
max_a = max(a[i], max_a);
for (int i = 1; i <= n; i++)
cnt[a[i]]++;
for (int i = 1; i <= max_a; i++)
sum[i] = sum[i - 1] + cnt[i];
for (int i = 1; i <= max_a; i++) {
if (!cnt[i]) continue;
long long cc = 0;
for (int j = 1; j <= max_a / i; j++) {
cc += (sum[min(max_a, (j + 1) * i - 1)] - sum[j * i - 1]) * j;
}
ans += 1ll * cc * cnt[i] * i;
}
long long total_sum = 0;
for (int i = 1; i <= n; i++) {
total_sum += a[i];
}
total_sum *= n;
printf("%lld", total_sum - ans);
return 0;
}