結果

問題 No.3250 最小公倍数
ユーザー LyricalMaestro
提出日時 2025-10-11 18:29:04
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,549 bytes
コンパイル時間 203 ms
コンパイル使用メモリ 82,764 KB
実行使用メモリ 410,912 KB
最終ジャッジ日時 2025-10-11 18:29:36
合計ジャッジ時間 30,134 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 1 WA * 16 TLE * 2 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/3250

import math
from collections import deque

MOD = 998244353

def main():
    N = int(input())
    A = list(map(int, input().split()))
    next_nodes = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = map(int, input().split())
        next_nodes[u - 1].append(v - 1)
        next_nodes[v - 1].append(u - 1)

    max_a = max(A)    
    sqrt_a = int(math.sqrt(max_a))
    primes = []
    is_prime = [j for j in range(max_a + 1)]
    for p in range(2, max_a + 1):
        if not is_prime[p]:
            continue
        if p <= sqrt_a:
            primes.append(p)
        x = 2 * p
        while x <= max_a:
            if is_prime[x] == x:
                is_prime[x] = p
            x += p
    
    A1 = [] # 一定以上    
    A2 = [] # 一定以下
    for a in A:
        b = {}
        while is_prime[a] != a and is_prime[a] <= sqrt_a:
            p = is_prime[a]
            if p not in b:
                b[p] = 0
            b[p] += 1
            a //= p

        A1.append(a)
        A2.append(b)

    # 一定以上のものについて
    stack = deque()
    parents = [-2] * N
    parents[0] = -1
    stack.append((0, 0))
    answer1 = [1] * N
    answer2 = [{} for _ in range(N)]
    answer1_set = [set() for _ in range(N)]
    while len(stack) > 0:
        v, index = stack.pop()
        if index == 0:
            answer1[v] *= A1[v]
            answer1[v] %= MOD
            answer1_set[v].add(A1[v])

            v_map = A2[v]
            for p, v_ind in v_map.items():
                if p not in answer2[v]:
                    answer2[v][p] = 0
                answer2[v][p] = max(answer2[v][p], v_ind)

        while index < len(next_nodes[v]):
            w = next_nodes[v][index]
            if w == parents[v]:
                index += 1
                continue

            parents[w] = v
            stack.append((v, index + 1))
            stack.append((w, 0))
            break

        if index == len(next_nodes[v]):
            p = parents[v]
            if p != -1:
                a_set1 = answer1_set[p]
                a_set2 = answer1_set[v]
                if len(a_set1) >= len(a_set2):
                    value = answer1[p]
                    for prime in a_set2:
                        if prime not in a_set1:
                            value *= prime
                            value %= MOD
                        a_set1.add(prime)
                    answer1[p] = value
                    answer1_set[p] = a_set1
                else:
                    value = answer1[v]
                    for prime in a_set1:
                        if prime not in a_set2:
                            value *= prime
                            value %= MOD
                        a_set2.add(prime)
                    answer1[p] = value
                    answer1_set[p] = a_set2

                v_map = answer2[v]
                for p_, v_ind in v_map.items():
                    if p_ not in answer2[p]:
                        answer2[p][p_] = 0
                    answer2[p][p_] = max(answer2[p][p_], v_ind)

    cache = {}
    for p in primes:
        v_array = [0] * 65
        p1 = 1
        for i in range(65):
            v_array[i] = p1
            p1 *= p
            p1 %= MOD
        cache[p] = v_array


    for i in range(N):
        answer = answer1[i]
        for p, v_ind in answer2[i].items():
            answer *= cache[p][v_ind]
            answer %= MOD
        print(answer)    




if __name__ == '__main__':
    main()
0