結果

問題 No.3250 最小公倍数
ユーザー 👑 loop0919
提出日時 2025-08-29 23:01:17
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,159 bytes
コンパイル時間 3,265 ms
コンパイル使用メモリ 300,984 KB
実行使用メモリ 35,312 KB
最終ジャッジ日時 2025-08-29 23:01:36
合計ジャッジ時間 7,914 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
==================== ORIGINAL PYTHON (do not remove) ====================

MOD = 998244353

from collections import defaultdict
from math import isqrt


def sieve(n: int):
    """エラトステネスの篩（O(n log log n)）"""
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, isqrt(n) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


def factorize(n: int, primes=None):
    """素因数分解（O(√n)）"""
    factorized = defaultdict(int)

    it = range(2, isqrt(n) + 1) if primes is None else primes

    for i in it:
        while n % i == 0:
            factorized[i] += 1
            n //= i

    if n > 1:
        factorized[n] += 1

    return factorized


N = int(input())
A = list(map(int, input().split()))

tree = [[] for _ in range(N)]

for _ in range(N - 1):
    u, v = map(int, input().split())
    tree[u - 1].append(v - 1)
    tree[v - 1].append(u - 1)

primes = sieve(10**6)


lcm = [factorize(A[i], primes) for i in range(N)]


def dfs(v, p):
    for u in tree[v]:
        if u == p:
            continue
        dfs(u, v)
        for k, val in lcm[u].items():
            lcm[v][k] = max(lcm[v][k], val)


dfs(0, -1)

for i in range(N):
    ans = 1
    for k, v in lcm[i].items():
        ans = (ans * pow(k, v, MOD)) % MOD
    print(ans)

========================================================================
*/

#include <bits/stdc++.h>
using namespace std;

static const long long MOD = 998244353LL;

vector<int> sieve(int n) {
    // エラトステネスの篩（O(n log log n)）
    vector<char> is_prime(n + 1, true);
    if (n >= 0) is_prime[0] = false;
    if (n >= 1) is_prime[1] = false;
    int lim = static_cast<int>(sqrt((long double)n));
    for (int i = 2; i <= lim; ++i) {
        if (is_prime[i]) {
            long long start = 1LL * i * i;
            for (long long j = start; j <= n; j += i) is_prime[(int)j] = false;
        }
    }
    vector<int> primes;
    for (int i = 2; i <= n; ++i) if (is_prime[i]) primes.push_back(i);
    return primes;
}

// 素因数分解：Python実装の「primes をそのまま全て舐める」挙動を厳密に踏襲
unordered_map<long long, int> factorize_with_primes(long long n, const vector<int>& primes) {
    unordered_map<long long, int> res;
    for (int p : primes) {
        while (n % p == 0) {
            res[p] += 1;
            n /= p;
        }
    }
    if (n > 1) res[n] += 1;
    return res;
}

long long mod_pow(long long a, long long e, long long mod) {
    long long r = 1 % mod;
    a %= mod;
    while (e > 0) {
        if (e & 1) r = (__int128)r * a % mod;
        a = (__int128)a * a % mod;
        e >>= 1;
    }
    return r;
}

int N;
vector<long long> A;
vector<vector<int>> tree;
vector<unordered_map<long long, int>> lcm_exp;

void dfs(int v, int p) {
    for (int u : tree[v]) {
        if (u == p) continue;
        dfs(u, v);
        for (const auto& kv : lcm_exp[u]) {
            long long k = kv.first;
            int val = kv.second;
            auto it = lcm_exp[v].find(k);
            if (it == lcm_exp[v].end()) {
                lcm_exp[v][k] = val;
            } else if (it->second < val) {
                it->second = val;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    A.resize(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    tree.assign(N, {});
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    vector<int> primes = sieve(1'000'000);
    lcm_exp.resize(N);
    for (int i = 0; i < N; ++i) {
        lcm_exp[i] = factorize_with_primes(A[i], primes);
    }

    dfs(0, -1);

    for (int i = 0; i < N; ++i) {
        long long ans = 1;
        for (const auto& kv : lcm_exp[i]) {
            long long k = kv.first;
            int e = kv.second;
            ans = (ans * mod_pow(k, e, MOD)) % MOD;
        }
        cout << ans << '\n';
    }

    return 0;
}
0