結果

問題 No.3250 最小公倍数
ユーザー miya145592
提出日時 2025-08-29 23:20:14
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,746 bytes
コンパイル時間 339 ms
コンパイル使用メモリ 82,320 KB
実行使用メモリ 630,192 KB
最終ジャッジ日時 2025-08-29 23:20:24
合計ジャッジ時間 5,156 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4 MLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

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):
    temp = n
    for i in prime_list:
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            idx = rev_list[i]
            arr[idx] = cnt

    if temp!=1:
        arr[L].add(temp)

def dfs(v, p):
    factorization(A[v], ans[v])
    for nv in G[v]:
        if nv==p:
            continue
        dfs(nv, v)
        for i in range(L):
            if ans[v][i] < ans[nv][i]:
                ans[v][i] = ans[nv][i]
        ans[v][L] |= ans[nv][L]

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 = []
rev_list = dict()
for i, p in enumerate(P):
    if p:
        prime_list.append(i)
        rev_list[i] = len(rev_list)
L = len(prime_list)
ans = [[0 for _ in range(L)] for _ in range(N)]
for i in range(N):
    ans[i].append(set())
dfs(0, -1)
for a in ans:
    tmp = 1
    for i in range(L):
        if a[i]>0:
            e = a[i]
            p = prime_list[i]
            tmp *= pow(p, e, MOD)
            tmp %= MOD
    for p in a[L]:
        tmp *= p
        tmp %= MOD
    print(tmp)
0