結果

問題 No.1917 LCMST
コンテスト
ユーザー ytft
提出日時 2022-04-30 14:07:44
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,400 bytes
コンパイル時間 429 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 301,060 KB
最終ジャッジ日時 2024-06-29 19:49:48
合計ジャッジ時間 9,499 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 TLE * 1 -- * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

class unionFind:
    def __init__(self,N):
        self.N=N
        self.parent=[-1 for i in range(N)]
        self.size=[1 for i in range(N)]
    def find(self,x):
        path=[x]
        while self.parent[path[-1]]!=-1:
            path.append(self.parent[path[-1]])
        for i in path[:-1]:
            self.parent[i]=path[-1]
        return path[-1]
    def unite(self,x,y):
        roots=sorted([self.find(x),self.find(y)],key=lambda _:self.parent[_])
        if roots[0]!=roots[1]:
            self.parent[roots[0]]=roots[1]
            self.size[roots[1]]+=self.size[roots[0]]
def gcd(a,b):
    return gcd(a%b,b%a) if min(a,b)*(a-b) else max(a,b)
def lcm(a,b):
	return a*b//gcd(a,b)
def divisors(n):
    ans=[]
    for i in range(1,n+1):
        if n%i==0:
            ans.append(i)
        if i**2>n:
            break
    k=len(ans)
    for i in range(k-1,-1,-1):
        if n//ans[i]>ans[k-1]:
            ans.append(n//ans[i])
    return ans
N=int(input())
A=list(map(int,input().split()))
M=max(A)
dp=[[] for i in range(M)]
for i in range(N):
	for j in divisors(A[i]):
		dp[j-1].append(i)
cand=[]
for i in range(M):
	dp[i]=sorted(dp[i],key=lambda x:A[x])
	for j in dp[i][1:]:
		cand.append([dp[i][0],j])
cand=sorted(cand,key=lambda x:lcm(A[x[0]],A[x[1]]))
U=unionFind(N)
ans=0
for i in cand:
	if U.find(i[0])!=U.find(i[1]):
		U.unite(i[0],i[1])
		ans+=lcm(A[i[0]],A[i[1]])
print(ans)
0