結果

問題 No.3250 最小公倍数
コンテスト
ユーザー i_taku
提出日時 2025-09-01 12:12:25
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,606 bytes
コンパイル時間 2,187 ms
コンパイル使用メモリ 211,420 KB
実行使用メモリ 822,348 KB
最終ジャッジ日時 2025-10-16 17:06:26
合計ジャッジ時間 10,108 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other MLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

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


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

    int N; cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    vector<vector<int>> g(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);
    }
    vector<int> primes;
    const int MAX = 1000001;
    vector<bool> is_prime(MAX, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i < MAX; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (int j = 2 * i; j < MAX; j += i) {
                is_prime[j] = false;
            }
        }
    }
    vector<map<int, int>> dp(N);
    for (int i = 0; i < N; i++) {
        int x = A[i];
        for (int p : primes) {
            if (p * p > x) break;
            while (x % p == 0) {
                dp[i][p]++;
                x /= p;
            }
        }
        if (x > 1) dp[i][x]++;   
    }

    auto dfs = [&](auto&& self, int v, int p) -> void {
        for (int nv : g[v]) {
            if (nv == p) continue;
            self(self, nv, v);
            for (auto [prime, cnt] : dp[nv]) {
                dp[v][prime] = max(dp[v][prime], cnt);
            }
        }
    };
    dfs(dfs, 0, -1);
    for (int i = 0; i < N; i++) {
        long long ans = 1;
        for (auto [prime, cnt] : dp[i]) {
            for (int j = 0; j < cnt; j++) {
                ans = (ans * (long long)prime) % 998244353;
            }
        }
        cout << ans << "\n";
    }
}
0