No.2497 GCD of LCMs
レベル :
/ AI推定難易度 : 1700
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 64
作問者 :
KumaTachiRen
/ テスター :
👑
AngrySadEight
タグ : / 解いたユーザー数 64
作問者 :
問題文最終更新日: 2023-09-11 11:52:50
English (AI translation)
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もしくは右上の雲マークをクリックしてアカウントを作成してください。