結果

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

ソースコード

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)
    
    sqrt_max_a = int(math.sqrt(max(A)))

    primes = []
    is_prime = [True] * (sqrt_max_a + 1)
    for p in range(2, sqrt_max_a + 1):
        if not is_prime[p]:
            continue
        
        primes.append(p)
        x = 2 * p
        while x <= sqrt_max_a:
            is_prime[x] = False
            x += p
    
    A1 = [] # 一定以上    
    A2 = [] # 一定以下
    for a in A:
        b = {}
        for p in primes:
            while a % p == 0:
                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]
            p_map = answer2[v]
            for p, v_ind in v_map.items():
                if p not in p_map:
                    p_map[p] = 0
                p_map[p] = max(p_map[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]
                p_map = answer2[p]
                for p_, v_ind in v_map.items():
                    if p_ not in p_map:
                        p_map[p_] = 0
                    p_map[p_] = max(p_map[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