题解

题面描述

给定 $n$ 个元素 $a_i$，它们的取值范围在 $1 \le a_i \le 10^5$。我们需要计算以下和式的值：

$S$ = $\sum_{1 \le i \le n}$ $\sum_{1 \le j \le n}$ $\left\lfloor \frac{a_i}{a_j} \right\rfloor$

题目内容

给定 $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≤i≤3} \sum_{1≤j≤3}[\dfrac{a_i}{a_j}]$

具体计算：

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

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

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

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