No.1917 LCMST
レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 69
作問者 :
とりゐ
/ テスター :
chineristAC
riano
タグ : / 解いたユーザー数 69
作問者 :
とりゐ
/ テスター :
chineristAC
riano
問題文最終更新日: 2022-06-24 23:43:47
問題文
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。