結果
問題 | No.2756 GCD Teleporter |
ユーザー |
![]() |
提出日時 | 2024-05-12 17:53:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 381 ms / 2,000 ms |
コード長 | 1,910 bytes |
コンパイル時間 | 315 ms |
コンパイル使用メモリ | 82,368 KB |
実行使用メモリ | 108,068 KB |
最終ジャッジ日時 | 2024-12-20 09:11:57 |
合計ジャッジ時間 | 10,876 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 36 |
ソースコード
class Factorization():def __init__(self, N):self.L = list(range(N + 1))for i in range(2, N + 1):if i != self.L[i]:continuefor j in range(2 * i, N + 1, i):self.L[j] = idef get(self, n):if n <= 1:return []D = []while n != 1:cnt = 0now = self.L[n]while n % now == 0:cnt += 1n //= nowD.append((now, cnt))return Dclass UnionFind():def __init__(self, n=1):self.par = [i for i in range(n)]self.rank = [0 for _ in range(n)]self.size = [1 for _ in range(n)]def find(self, x):if self.par[x] == x:return xelse:self.par[x] = self.find(self.par[x])return self.par[x]def union(self, x, y):x = self.find(x)y = self.find(y)if x != y:if self.rank[x] < self.rank[y]:x, y = y, xif self.rank[x] == self.rank[y]:self.rank[x] += 1self.par[y] = xself.size[x] += self.size[y]def is_same(self, x, y):return self.find(x) == self.find(y)def get_size(self, x):x = self.find(x)return self.size[x]N = int(input())A = list(map(int, input().split()))M = 2 * 10 ** 5 + 5F = Factorization(M)now = Nfrom collections import *D = defaultdict(int)for a in A:for k, v in F.get(a):if k not in D:D[k] = nownow += 1U = UnionFind(now)mi = 10 ** 18for i, a in enumerate(A):for k, v in F.get(a):mi = min(mi, k)U.union(i, D[k])S = set()for i in range(N):S.add(U.find(i))if mi == 2:print((len(S) - 1) * 2)else:print(min(2 * len(S), mi * (len(S) - 1)))