No.1233 割り切れない気持ち
レベル : / 実行時間制限 : 1ケース 3.153秒 / メモリ制限
: 315 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 158
作問者 :
CuriousFairy315
/ テスター :
QCFium
タグ : / 解いたユーザー数 158
作問者 :
CuriousFairy315
/ テスター :
QCFium
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。