結果

問題 No.3250 最小公倍数
ユーザー miya145592
提出日時 2025-08-29 22:11:07
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,152 bytes
コンパイル時間 331 ms
コンパイル使用メモリ 82,660 KB
実行使用メモリ 244,728 KB
最終ジャッジ日時 2025-08-29 22:11:45
合計ジャッジ時間 33,627 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 TLE * 13 -- * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

def factorization(n):
    arr = defaultdict(int)
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        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):
    ans[v] = factorization(A[v])
    for nv in G[v]:
        if nv==p:
            continue
        dfs(nv, v)
        for key in ans[nv]:
            if ans[v][key]<ans[nv][key]:
                ans[v][key] = ans[nv][key]

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)
ans = [defaultdict(int) for _ in range(N)]
dfs(0, -1)
for a in ans:
    tmp = 1
    for p in a:
        e = a[p]
        tmp *= pow(p, e, MOD)
        tmp %= MOD
    print(tmp)
0