No.1233 Indivisible Feelings
タグ : / 解いたユーザー数 172
作問者 :
CuriousFairy315
/ テスター :
QCFium
Problem Statement
31536000 has a sequence $A$ consisting of $N$ integers. The $i$-th value of $A$ is $A_i$.
31536000 loves relationships of multiples and divisors, and feels happy when one of two numbers divides the other.
Conversely, when two numbers do not divide, 31536000 is left with a somewhat unsettled, "indivisible" feeling.
For two numbers $(x, y)$, the strength of the indivisible feeling is defined as the remainder when $x$ is divided by $y$.
Find the strength of the indivisible feeling of $(A_i, A_j)$ for all $i, j$ satisfying $1 \leq i, j \leq N$, and output their sum.
Input
$N$ $A_1$ $A_2$ $\cdots$ $A_N$
$1 \leq N \leq 2 \cdot 10^5$
$1 \leq A_i \leq 2 \cdot 10^5$
Output
Output the sum of the strengths of the indivisible feelings.
Sample
Sample 1
Input
3 1 5 3
Output
7
For the $9$ pairs $(1, 1), (1, 5), (1, 3), (5, 1), (5, 5), (5, 3), (3, 1), (3, 5), (3, 3)$, the respective indivisible feelings are $0, 1, 1, 0, 0, 2, 0, 3, 0$, so the sum is $7$.
Sample 2
Input
9 9 9 9 9 9 9 9 9 9
Output
0
It is possible that the division is exact for every combination.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。