結果
問題 |
No.1917 LCMST
|
ユーザー |
|
提出日時 | 2025-07-15 18:06:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,247 ms / 4,000 ms |
コード長 | 1,850 bytes |
コンパイル時間 | 542 ms |
コンパイル使用メモリ | 82,364 KB |
実行使用メモリ | 308,876 KB |
最終ジャッジ日時 | 2025-07-15 18:08:13 |
合計ジャッジ時間 | 63,279 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
class UnionFind(): # 初期化 def __init__(self, n): self.par = [-1] * n self.rank = [0] * n self.siz = [1] * n # 根を求める def root(self, x): if self.par[x] == -1: return x # x が根の場合は x を返す else: self.par[x] = self.root(self.par[x]) # 経路圧縮 return self.par[x] # x と y が同じグループに属するか (根が一致するか) def issame(self, x, y): return self.root(x) == self.root(y) # x を含むグループと y を含むグループを併合する def unite(self, x, y): # x 側と y 側の根を取得する rx = self.root(x) ry = self.root(y) if rx == ry: return False # すでに同じグループのときは何もしない # union by rank if self.rank[rx] < self.rank[ry]: # ry 側の rank が小さくなるようにする rx, ry = ry, rx self.par[ry] = rx # ry を rx の子とする if self.rank[rx] == self.rank[ry]: # rx 側の rank を調整する self.rank[rx] += 1 self.siz[rx] += self.siz[ry] # rx 側の siz を調整する return True # x を含む根付き木のサイズを求める def size(self, x): return self.siz[self.root(x)] from math import gcd n = int(input()) a = list(map(int, input().split())) a.sort() d = [0] * 100001 ans = 0 for x in a: if d[x]: ans += x else: d[x] = 1 e = [] for i in range(100000, 0, -1): m = -1 for j in range(i, 100001, i): if d[j]: if m == -1: m = j else: e.append((m * j // gcd(m, j), m, j)) e.sort() uf = UnionFind(100001) for l, u, v in e: if uf.issame(u, v): continue uf.unite(u, v) ans += l print(ans)