結果
問題 | No.2497 GCD of LCMs |
ユーザー |
![]() |
提出日時 | 2024-01-13 18:39:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 137 ms / 2,000 ms |
コード長 | 631 bytes |
コンパイル時間 | 194 ms |
コンパイル使用メモリ | 82,688 KB |
実行使用メモリ | 77,056 KB |
最終ジャッジ日時 | 2024-09-28 01:42:16 |
合計ジャッジ時間 | 1,990 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
from math import gcd lcm = lambda a,b: a//gcd(a,b)*b import sys readline = sys.stdin.readline n,m = map(int,readline().split()) *a, = map(int,readline().split()) g = [[] for _ in range(n)] for _ in range(m): u,v = map(int,readline().split()) g[u-1].append(v-1) g[v-1].append(u-1) inq = [0]*n inq[0] = 1 dist = [0]*n dist[0] = a[0] q = [0] while q: v = q.pop() inq[v] = 0 for w in g[v]: nc = gcd(lcm(dist[v],a[w]),dist[w]) if nc == dist[w]: continue dist[w] = gcd(nc,dist[w]) if inq[w] == 0: inq[w] = 1 q.append(w) for i in dist:print(i%998244353)