思路与题解

把所有相同取值聚合。设 $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$ 的区间分块：

题目内容

给定$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$。

样例1

输入

3
1 2 3

输出

9

说明

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

$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$