問題一覧 > 通常問題

No.3827 MST on LCM Graph

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 15
作問者 : shiomusubi496 / テスター : Rho 259-Momone okkuu
お気に入りにしたユーザー ProblemId : 14230 / 自分の提出
問題文最終更新日: 2026-11-21 15:40:31
TSG LIVE! 17 プログラミングコンテスト (順位表) の他の問題:

問題文

長さ $N$ の正整数列 $A=(A_1, A_2, \ldots, A_N)$ が与えられます。

頂点 $u, v$ を結ぶ辺の重みが $\mathrm{lcm}(A_u, A_v)$ であるような頂点数 $N$ の完全グラフ $G$ の最小全域木の重みを求めてください。

入力

$N$
$A_1\ A_2\ \ldots\ A_N$
  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq A_i \leq 2 \times 10^5$ $(1 \leq i \leq N)$
  • 入力は全て整数

出力

$G$ の最小全域木の重みを一行に出力してください。

最後に改行してください。

サンプル

サンプル1
入力
4
6 9 12 18
出力
48

例えば,次の 3 つの辺からなる全域木があります。

  • 辺 $(1, 2)$ :重みは $\mathrm{lcm}(A_1, A_2) = 18$
  • 辺 $(1, 3)$ :重みは $\mathrm{lcm}(A_1, A_3) = 12$
  • 辺 $(2, 4)$ :重みは $\mathrm{lcm}(A_2, A_4) = 18$

これが最小全域木の一つであることが証明できるため、$18+12+18=48$ を出力します。

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

サンプル3
入力
10
54371 40075 150258 164505 5893 123584 57309 117727 159897 94222
出力
5659131652

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