問題一覧 > 通常問題

No.2046 Ans Mod? Mod Ans!

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 76
作問者 : koboshikoboshi / テスター : ShirotsumeShirotsume 👑 hitonanodehitonanode
3 ProblemId : 6769 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-08-09 22:12:42

ストーリー

小星さんは競技プログラミングの問題を解いています。ある問題には次のように書かれていました。

答えは非常に大きくなる可能性があるので、答えで $10^9+7$ を割った余りを出力してください。

小星さんはこれを「答えを $10^9+7$ で割った余りを出力してください」だと勘違いしたため、解くことができませんでした。

悲しい気持ちになった小星さんは、正答と小星さんの解答の誤差について調べることにしました。答えが $X$、割る数が $Y$ のとき、この誤差は $|(X\bmod{Y})-(Y\bmod{X})|$ と表されます。

小星さんはこれをもとに次のような問題を作りました。

問題文

相異なる正の整数 $A_1,A_2,\ldots,A_N$ が与えられるので

$$\sum_{i=1}^{N-1}\sum_{j=i+1}^N|(A_i\bmod{A_j})-(A_j\bmod{A_i})|$$

の値を求めてください。

ただし $a\bmod{b}$ は $a$ を $b$ で割った余りを表します。

実行時間制限に注意してください。

制約

  • $2\le N\le 2\times 10^5$
  • $1\le A_i\le 2\times 10^5$
  • $i\ne j$ ならば $A_i\ne A_j$
  • 入力はすべて整数

入力

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

出力

答えを出力してください。

サンプル

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

$|(3\bmod{5})-(5\bmod{3})|=|3-2|=1$ です。

サンプル2
入力
3
1 11 111
出力
12

サンプル3
入力
9
1 9 2 8 3 7 4 6 5
出力
83

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