思路与题解

把所有相同取值聚合。设 $U=\max(a_i)$ ，定义频次数组 $cnt[x]$ 表示值为 $x$ 的元素个数。则

$S$ = $\sum_{y=1}^{U} cnt[y]\cdot H(y)$ , $\quad$

$H(y)$ = $\sum_{x=1}^{U} cnt[x]$ $\cdot \left\lfloor \dfrac{x}{y}\right\rfloor.$

对固定的 $y$ ，当 $x\in [ky,(k+1)y-1]$ 时有 $\left\lfloor \dfrac{x}{y}\right\rfloor$ = $k$ 。因此可以把 $[1,U]$ 按长度为 $y$ 的区间分块：

P3729.第3题-小红求和

1000ms

Difficulty: 7

所属公司 : 蚂蚁

算法与标签>前缀和

给定 $n$ 个元素 $a_i$ ，要求计算以下表达式的值:

$S=\sum_{1 \leq i \leq n} \sum_{1 \leq j \leq n}\left\lfloor\frac{a_{i}}{a_{j}}\right\rfloor$

第一行包含一个整数 $n$ ，表示元素的个数，满足 $1≤n≤10^5$

第二行包含 $n$ 个整数 $a_1,a_2,..a_n$ ，其中 $1≤a_i≤10^5$

输出一个整数，表示计算得到的值 $S$ 。

输入

3
1 2 3

输出

说明

对于输入的样例，计算过程如下:

$S=\sum_{1 \leq i \leq 3} \sum_{1 \leq j \leq 3}\left\lfloor\frac{a_{i}}{a_{j}}\right\rfloor$

具体计算:

当 $i=1$ 时: $1+0+0=1$

当 $i=2$ 时: $2+1+0=3$

当 $i=3$ 时: $3+1+1=5$

将所有结果相加，得到 $S=1+3+5=9$

输入

预期输出（选填）