No.3250 Least Common Multiple
trqs
yukicoder
問題文最終更新日: 2025-08-07 14:23:28
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 480 (Gemini Tester)
(順位表)
の他の問題:
Remarks
As a first-time experiment, we had Gemini 2.5Pro act as the tester for this problem.
Problem Statement
You are given a tree with $n$ vertices rooted at $1$. Each vertex $i$ has a weight $a_i$. For every $1 \le i \le n$, find the least common multiple of the weights of all vertices in the subtree rooted at vertex $i$, and output that value modulo $998244353$.
Input
$n$
$a_1\ a_2 \cdots\ a_n$
$u_1\ v_1$
$u_2\ v_2$
$\cdots$
$u_{n-1}\ v_{n-1}$
Output
Output $n$ lines. On the $i$-th line, output the least common multiple of the weights of all vertices in the subtree rooted at vertex $i$, modulo $998244353$.
Sample
Sample 1
Input
10 38409 56089 77656 65616 194443 82271 145333 20534 144963 106211 1 4 1 2 2 3 2 5 7 10 3 6 4 8 5 9 5 7
Output
399809643 164611798 399370658 673679472 887817188 82271 462297968 20534 144963 106211
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。