問題一覧 > 通常問題

No.1233 Indivisible Feelings

レベル : / AI推定難易度 : 1450 / 実行時間制限 : 1ケース 3.153秒 / メモリ制限 : 315 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 172
作問者 : CuriousFairy315 / テスター : QCFium
お気に入りにしたユーザー ProblemId : 3265 / 自分の提出
問題文最終更新日: 2019-07-31 02:22:55
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 266 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。