結果
問題 |
No.2497 GCD of LCMs
|
ユーザー |
![]() |
提出日時 | 2023-10-06 23:02:50 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 331 ms / 2,000 ms |
コード長 | 1,668 bytes |
コンパイル時間 | 2,758 ms |
コンパイル使用メモリ | 79,216 KB |
実行使用メモリ | 58,244 KB |
最終ジャッジ日時 | 2024-07-26 16:53:59 |
合計ジャッジ時間 | 6,140 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
import java.io.BufferedReader; import java.io.InputStreamReader; import java.math.BigInteger; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.List; import java.util.Queue; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] sa = br.readLine().split(" "); int n = Integer.parseInt(sa[0]); int m = Integer.parseInt(sa[1]); sa = br.readLine().split(" "); BigInteger[] a = new BigInteger[n]; for (int i = 0; i < n; i++) { a[i] = new BigInteger(sa[i]); } List<List<Integer>> list = new ArrayList<>(n); for (int i = 0; i < n; i++) { list.add(new ArrayList<>()); } for (int i = 0; i < m; i++) { sa = br.readLine().split(" "); int u = Integer.parseInt(sa[0]) - 1; int v = Integer.parseInt(sa[1]) - 1; list.get(u).add(v); list.get(v).add(u); } br.close(); BigInteger[] dp = new BigInteger[n]; boolean[] visit = new boolean[n]; Queue<Integer> que = new ArrayDeque<>(); que.add(0); dp[0] = a[0]; visit[0] = true; while (!que.isEmpty()) { int cur = que.poll(); for (int next : list.get(cur)) { BigInteger g1 = dp[cur].gcd(a[next]); BigInteger v1 = dp[cur].multiply(a[next]).divide(g1); if (visit[next]) { BigInteger g2 = v1.gcd(dp[next]); if (!g2.equals(dp[next])) { dp[next] = g2; que.add(next); } } else { visit[next] = true; dp[next] = v1; que.add(next); } } } BigInteger mod = BigInteger.valueOf(998244353); for (int i = 0; i < n; i++) { System.out.println(dp[i].mod(mod).intValue()); } } }