結果
問題 | No.1917 LCMST |
ユーザー | shinichi |
提出日時 | 2023-01-29 17:35:36 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,074 bytes |
コンパイル時間 | 145 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 548,068 KB |
最終ジャッジ日時 | 2024-06-29 13:49:26 |
合計ジャッジ時間 | 9,180 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 85 ms
76,708 KB |
testcase_01 | AC | 80 ms
75,612 KB |
testcase_02 | AC | 81 ms
75,392 KB |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | AC | 81 ms
76,392 KB |
testcase_09 | MLE | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
ソースコード
from collections import defaultdict from math import gcd lcm = lambda x, y: x * y // gcd(x, y) class Eratosthenes(): def __init__(self, size): self.size = size self.isprime = [True] * size self.minfactor = [-1] * size self.mobius = [1] * size self.isprime[1] = False self.minfactor[1] = 1 self.eratosthenes() # 初めに篩にかけて,minfactorとisprimeを生成 def eratosthenes(self): for p in range(2, self.size): if not self.isprime[p]: continue self.minfactor[p] = p self.mobius[p] = -1 for q in range(p+p, self.size, p): self.isprime[q] = False if self.minfactor[q] == -1: self.minfactor[q] = p if (q//p) % p == 0: self.mobius[q] = 0 else: self.mobius[q] = -self.mobius[q] # 高速素因数分解 def prime_factorize(self, number): assert 1 <= number <= self.size factors = defaultdict(int) while number != 1: factors[self.minfactor[number]] += 1 number //= self.minfactor[number] return factors # 高速約数列挙 def divisors(self, number): res = [1] factors = self.prime_factorize(number) for p, cnt in factors.items(): # 追加前の大きさを保存 res_size = len(res) for i in range(res_size): pp = 1 for j in range(cnt): pp *= p res.append(res[i]*pp) return res class UnionFind(object): def __init__(self, size): self.parent = [-1] * size def union(self, x, y): x, y = self.root(x), self.root(y) if x == y: return False if self.parent[x] > self.parent[y]: x, y = y, x self.parent[x] += self.parent[y] self.parent[y] = x return True def root(self, x): if self.parent[x] < 0: return x self.parent[x] = self.root(self.parent[x]) return self.parent[x] def same(self, x, y): return self.root(x) == self.root(y) def size(self, x): return - self.parent[self.root(x)] def group_count(self): return [p < 0 for p in self.parent].count(True) N = int(input()) A = list(map(int, input().split())) edges = [] era = Eratosthenes(2 * 10 ** 5) to_idx = defaultdict(lambda: -1) for i, a in enumerate(A): if to_idx[a] != -1: edges.append((i, to_idx[a], a)) else: to_idx[a] = i D = [[] for _ in range(10 ** 5 + 1)] for i, a in enumerate(A): for d in era.divisors(a): D[d].append((a, i)) for d in D: if not d: continue min_val, min_idx = min(d) for other_val, other_idx in d: edges.append((min_idx, other_idx, lcm(min_val, other_val))) ans = 0 uf = UnionFind(N) edges.sort() for u, v, w in edges: if uf.union(u, v): ans += w print(ans)