結果

問題 No.14 最小公倍数ソート
ユーザー nsd_fb
提出日時 2015-02-20 09:18:46
言語 Python2
(2.7.18)
結果
AC  
実行時間 503 ms / 5,000 ms
コード長 1,030 bytes
コンパイル時間 138 ms
コンパイル使用メモリ 7,072 KB
実行使用メモリ 21,296 KB
最終ジャッジ日時 2024-06-23 21:22:22
合計ジャッジ時間 7,631 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import fractions
import heapq

def lcm(a, b):
    return a / fractions.gcd(a, b) * b

MAX_A = 10000

N = input()
A = map(int, raw_input().split())

divisor = [[] for _ in xrange(N)]
queue = [[] for _ in xrange(MAX_A + 1)]
used = [False] * N

for i, a in enumerate(A):
    j = 1
    
    while j * j <= a:
        if a % j == 0:
            divisor[i].append(j)
            heapq.heappush(queue[j], (a, i))
            
            if a / j != j:
                divisor[i].append(a / j)
                heapq.heappush(queue[a / j], (a, i))

        j += 1


ans = range(N)
for i in xrange(N - 1):
    index = ans[i]
    used[index] = True
    best = (float("inf"), -1, -1)

    for d in divisor[index]:
        que = queue[d]
        while que:
            tmp = que[0]
            if used[tmp[1]]:
                heapq.heappop(que)
                continue

            best = min(best, (lcm(A[index], tmp[0]),  tmp[0], tmp[1]))
            break

    ans[i + 1] = best[2]

print ' '.join(map(lambda index: str(A[index]), ans))
0