結果

問題 No.3250 最小公倍数
コンテスト
ユーザー miya145592
提出日時 2025-08-29 22:19:01
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,519 bytes
コンパイル時間 692 ms
コンパイル使用メモリ 82,104 KB
実行使用メモリ 560,980 KB
最終ジャッジ日時 2025-10-16 16:22:09
合計ジャッジ時間 8,090 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other MLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

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):
    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)
P = prime(10**3)
prime_list = []
for i, p in enumerate(P):
    if p:
        prime_list.append(i)
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