問題一覧 > 通常問題

No.1917 LCMST

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 48
作問者 : とりゐとりゐ / テスター : chineristACchineristAC rianoriano
15 ProblemId : 7820 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-25 23:34:14

問題文

$N$ 頂点の完全グラフ $G$ を考えます.頂点 $i$ と頂点 $j$ をつなぐ辺の重みは $A_i$ と $A_j$ の最小公倍数です.$G$ の最小全域木に含まれる辺の重みの和を求めてください.

入力

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

  • $2\leq N\leq 10^6$
  • $1\leq A_i\leq 10^5$
  • 入力は全て整数である

出力

最小全域木に含まれる辺の重みの和を求めてください.

サンプル

サンプル1
入力
3
2 3 4
出力
10

$\mathrm{lcm}(a,b)$ で $a$ と $b$ の最小公倍数を表すものとします.
頂点 $1$ と頂点 $2$ の間に重み $\mathrm{lcm}(2,3)=6$ の辺,頂点 $1$ と頂点 $3$ の間に重み $\mathrm{lcm}(2,4)=4$ の辺を貼ることで全域木の辺の重みの和は $10$ になり,これが最小です.

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

サンプル3
入力
5
593 401 467 241 227
出力
386354

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