結果

問題 No.3250 最小公倍数
ユーザー 👑 loop0919
提出日時 2025-08-29 22:57:12
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,349 bytes
コンパイル時間 520 ms
コンパイル使用メモリ 82,380 KB
実行使用メモリ 76,160 KB
最終ジャッジ日時 2025-08-29 22:57:18
合計ジャッジ時間 6,271 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

from collections import defaultdict
from math import isqrt


def sieve(n: int):
    """エラトステネスの篩（O(n log log n)）"""
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, isqrt(n) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


def factorize(n: int, primes=None):
    """素因数分解（O(√n)）"""
    factorized = defaultdict(int)

    it = range(2, isqrt(n) + 1) if primes is None else primes

    for i in it:
        while n % i == 0:
            factorized[i] += 1
            n //= i

    if n > 1:
        factorized[n] += 1

    return factorized


N = int(input())
A = list(map(int, input().split()))

tree = [[] for _ in range(N)]

for _ in range(N - 1):
    u, v = map(int, input().split())
    tree[u - 1].append(v - 1)
    tree[v - 1].append(u - 1)

primes = sieve(10**6)


lcm = [factorize(A[i], primes) for i in range(N)]


def dfs(v, p):
    for u in tree[v]:
        if u == p:
            continue
        dfs(u, v)
        for k, val in lcm[u].items():
            lcm[v][k] = max(lcm[v][k], val)


dfs(0, -1)

for i in range(N):
    ans = 1
    for k, v in lcm[i].items():
        ans = (ans * pow(k, v, MOD)) % MOD
    print(ans)
0