結果

問題 No.3250 最小公倍数
コンテスト
ユーザー miya145592
提出日時 2025-08-29 23:02:18
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,213 bytes
コンパイル時間 9,943 ms
コンパイル使用メモリ 473,076 KB
実行使用メモリ 813,440 KB
最終ジャッジ日時 2025-10-16 16:33:27
合計ジャッジ時間 16,903 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other MLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using namespace boost::multiprecision;

using BigInt = cpp_int;
const int MOD = 998244353;

int N;
vector<BigInt> A;
vector<vector<int>> G;
vector<BigInt> ans;

// 任意精度整数版 GCD
BigInt gcdBig(BigInt a, BigInt b) {
    while (b != 0) {
        BigInt t = b;
        b = a % b;
        a = t;
    }
    return a;
}

// DFSで部分木のLCMを計算
void dfs(int v, int p) {
    ans[v] = A[v];
    for (int nv : G[v]) {
        if (nv == p) continue;
        dfs(nv, v);
        BigInt g = gcdBig(ans[v], ans[nv]);
        ans[v] = (ans[v] / g) * ans[nv];  // LCM(ans[v], ans[nv])
    }
}

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

    cin >> N;
    A.resize(N);
    for (int i = 0; i < N; i++) {
        long long tmp;
        cin >> tmp;
        A[i] = tmp; // cpp_int に代入
    }

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

    ans.assign(N, 0);
    dfs(0, -1);

    for (int i = 0; i < N; i++) {
        cout << (ans[i] % MOD) << "\n";
    }
}
0