結果

問題 No.3250 最小公倍数
ユーザー miya145592
提出日時 2025-08-30 00:08:23
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,562 bytes
コンパイル時間 454 ms
コンパイル使用メモリ 82,100 KB
実行使用メモリ 188,000 KB
最終ジャッジ日時 2025-08-30 00:08:54
合計ジャッジ時間 25,625 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 17 TLE * 2 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

# エラトステネスの篩
def prime(n):
    is_prime = [True] * (n + 1)
    is_prime[0], is_prime[1] = False, False
    for i in range(2, int(math.sqrt(n)) + 1):
        if is_prime[i]:
            for j in range(2 * i, n + 1, i):
                is_prime[j] = False
    return is_prime

def factorization(n):
    arr = defaultdict(int)
    temp = n
    for i in prime_list:
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt

    if temp!=1:
        arr[temp] = 1
    
    if arr==[]:
        arr[n] = 1

    return arr

def dfs(v, p):
    ret = factorization(A[v])
    for nv in G[v]:
        if nv==p:
            continue
        tmp = dfs(nv, v)
        if len(ret)<len(tmp):
            ret, tmp = tmp, ret
        for key in tmp:
            if ret[key]<tmp[key]:
                ret[key] = tmp[key]
    for p in ret:
        e = ret[p]
        ans[v] *= pow(p, e, MOD)
        ans[v] %= MOD
    return ret

from collections import defaultdict
import sys
import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
MOD = 998244353
N = int(input())
A = list(map(int, input().split()))
G = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = map(int, input().split())
    u-=1
    v-=1
    G[u].append(v)
    G[v].append(u)
P = prime(10**3)
prime_list = []
for i, p in enumerate(P):
    if p:
        prime_list.append(i)
ans = [1 for _ in range(N)]
dfs(0, -1)
for a in ans:
    print(a)
0