問題一覧 > 通常問題

No.2497 GCD of LCMs

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 64
作問者 : KumaTachiRen / テスター : 👑 AngrySadEight
お気に入りにしたユーザー ProblemId : 9373 / 自分の提出
問題文最終更新日: 2023-09-11 11:52:50
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 407 (順位表) の他の問題:

Problem Statement

There is a connected simple undirected graph $G$ with $N$ vertices and $M$ edges. The $i\ (1\leq i\leq M)$-th edge connects vertices $U_i,V_i$. Also, an integer is written on each vertex, and the number written on vertex $i\ (1\leq i\leq N)$ is $A_i$. For each of $x=1,2,\dots,N$, solve the following problem.

  • Problem: For a simple path (a path that does not pass through the same vertex more than once) from vertex $1$ to vertex $x$, define its score as the least common multiple of all the integers written on the vertices contained in that simple path. Find the greatest common divisor of the scores of all simple paths from vertex $1$ to vertex $x$, modulo $998244353$.

Input

$N\ M$
$A_1\ A_2\ \dots\ A_N$
$U_1\ V_1$
$U_2\ V_2$
$\vdots$
$U_M\ V_M$

  • $1\leq N\leq 250$
  • $N-1\leq M\leq\min\left(8000,\frac{N(N-1)}{2}\right)$
  • $1\leq A_i\lt 998244353$
  • $1\leq U_i\lt V_i\leq N$
  • If $i\neq j$, then $(U_i,V_i)\neq(U_j,V_j)$.
  • The given graph is connected.
  • All input values are integers.

Output

Output $N$ lines. On the $i$-th line, output the answer for $x=i$. Print a newline at the end.

Sample

Sample 1
Input
4 4
3 4 6 9
1 2
1 3
2 4
3 4
Output
3
12
6
18

  • The only possible simple path from vertex $1$ to $1$ is $[1]$, and its score is $3$, so the answer is $3$.
  • The possible simple paths from vertex $1$ to $2$ are $[1,2],[1,3,4,2]$, with scores $12,36$ respectively, so the answer is $12$.
  • The possible simple paths from vertex $1$ to $3$ are $[1,3],[1,2,4,3]$, with scores $6,36$ respectively, so the answer is $6$.
  • The possible simple paths from vertex $1$ to $4$ are $[1,2,4],[1,3,4]$, with scores $36,18$ respectively, so the answer is $18$.

Sample 2
Input
5 4
164493406 49276361 366324377 764544595 615989488
1 2
2 3
3 4
4 5
Output
164493406
120205690
108232323
103692775
101734306

Output the remainder modulo $998244353$.

Sample 3
Input
8 20
785470077 742424363 266929410 601820340 936427390 852239977 812821450 40172340
5 8
5 6
2 7
2 8
1 6
4 5
3 8
1 8
1 3
3 6
2 6
1 7
4 7
1 4
5 7
1 5
4 6
1 2
3 7
2 3
Output
785470077
453182908
816474233
856799369
288800012
205327740
241617414
468866145

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。