Max/Min

题目描述

给定长度为 $N$ 的序列 $A=(A_1,\ldots,A_N)$。 求 $\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^{N}\left\lfloor\frac{\max(A_i,A_j)}{\min(A_i,A_j)}\right\rfloor$。 这里，$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。例如，$\lfloor 3.14 \rfloor=3$ 和 $\lfloor 2 \rfloor=2$。

输入格式

输入从标准输入按以下格式给出： $N$ $A_1$ $\ldots$ $A_N$

输出格式

输出答案。

3
3 1 4

8

6
2 7 1 8 2 8

53

12
3 31 314 3141 31415 314159 2 27 271 2718 27182 271828

592622

提示

$2 \leq N \leq 2\times 10^5$ $1 \leq A_i \leq 10^6$ 所有输入值均为整数。所求的值为 $\left\lfloor\frac{\max(3,1)}{\min(3,1)}\right\rfloor + \left\lfloor\frac{\max(3,4)}{\min(3,4)}\right\rfloor + \left\lfloor\frac{\max(1,4)}{\min(1,4)}\right\rfloor\\ =\left\lfloor\frac{3}{1}\right\rfloor + \left\lfloor\frac{4}{3}\right\rfloor + \left\lfloor\frac{4}{1}\right\rfloor\\ =3+1+4\\ =8$.

标签: AtCoder|abc356E

来源

AtCoder|abc356E