← 返回题目列表

AtCoder · abc356_e

H. 最大/最小

中文机器翻译题面 查看原题

分数: 475 点

问题陈述

给你一个序列 A=(A_1,\ldots,A_N) 长度 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.

约束

  • 2 \leq N \leq 2\times 10^5
  • 1 \leq A_i \leq 10^6
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 \ldots A_N

输出

打印答案。


示例输入 1

3
3 1 4

示例输出 1

8

寻求的值为

\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.


示例输入 2

6
2 7 1 8 2 8

示例输出 2

53

示例输入 3

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

示例输出 3

592622