問題一覧 > 通常問題

No.1233 割り切れない気持ち

レベル : / 実行時間制限 : 1ケース 3.153秒 / メモリ制限 : 315 MB / 通常問題
タグ : / 解いたユーザー数 110
作問者 : CuriousFairy315CuriousFairy315 / テスター : QCFiumQCFium
29 ProblemId : 3265 / 出題時の順位表
問題文最終更新日: 2019-07-31 02:22:55

問題文

31536000は、$N$個の整数が書かれた数列$A$を持っています。$A$の$i$番目の値は$A_i$です。
31536000は倍数や約数の関係が好きであり、ある2つの数が割り切れると嬉しい気持ちになります。
逆に、2つの数が割り切れないとどこか割り切れない気持ちになります。
ある2つの数$(x, y)$について、割り切れない気持ちの強さを$x$を$y$で割った余りと定義します。
この時、$1 \leq i, j \leq N$を満たす全ての$i, j$に対して$(A_i, A_j)$の割り切れない気持ちの強さを求め、その総和を出力してください。

入力

$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$

出力

割り切れない気持ちの強さの総和を出力してください。

サンプル

サンプル1
入力
3
1 5 3
出力
7

$(1, 1), (1, 5), (1, 3), (5, 1), (5, 5), (5, 3), (3, 1), (3, 5), (3, 3)$の$9$通りに対してそれぞれの割り切れない気持ちは$0, 1, 1, 0, 0, 2, 0, 3, 0$なので、総和は$7$となります。

サンプル2
入力
9
9 9 9 9 9 9 9 9 9
出力
0

全ての組み合わせで割り切れる場合もあります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。