結果

問題 No.3250 最小公倍数
ユーザー jiangxinyang
提出日時 2025-08-06 11:12:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,683 ms / 2,000 ms
コード長 3,756 bytes
コンパイル時間 1,250 ms
コンパイル使用メモリ 96,448 KB
実行使用メモリ 135,296 KB
最終ジャッジ日時 2025-08-29 20:52:24
合計ジャッジ時間 16,963 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

// by gemini 2.5 pro

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <numeric>

// using namespace std; を使う代わりに、必要なものだけを宣言
using std::cin;
using std::cout;
using std::vector;
using std::map;
using std::max;
using std::swap;

using ll = long long;

// 問題で指定された剰余
const int MOD = 998244353;
// a_i の最大値 + 5
const int MAX_A = 1000005;

// 高速な素因数分解のための前処理用配列
vector<int> min_prime;

/**
 * @brief エラトステネスの篩を用いて、nまでの各数の最小素因数を求める
 * @param n 上限値
 */
void sieve(int n) {
    min_prime.assign(n + 1, 0);
    for (int i = 2; i <= n; ++i) {
        if (min_prime[i] == 0) { // iが素数
            min_prime[i] = i;
            for (ll j = (ll)i * i; j <= n; j += i) {
                if (min_prime[j] == 0) {
                    min_prime[j] = i;
                }
            }
        }
    }
}

/**
 * @brief 前処理したテーブルを使い、数nを高速に素因数分解する
 * @param n 素因数分解する数
 * @return map<素因数, 指数>
 */
map<int, int> factorize(int n) {
    map<int, int> factors;
    if (n <= 1) return factors;
    while (n > 1) {
        factors[min_prime[n]]++;
        n /= min_prime[n];
    }
    return factors;
}

/**
 * @brief 繰り返し二乗法で base^exp % MOD を計算する
 */
ll power(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

int N;
vector<int> A;
vector<vector<int>> adj;
vector<map<int, int>> factors;
vector<ll> ans;

/**
 * @brief DFSで部分木のLCMを計算する
 * @param u 現在の頂点
 * @param p 親の頂点
 * @return 頂点uの部分木のLCMの素因数分解マップ
 */
map<int, int> dfs(int u, int p) {
    // まず自分自身の重みの素因数でマップを初期化
    map<int, int> res_map = factors[u];

    for (int v : adj[u]) {
        if (v == p) continue;
        
        // 子vの部分木の素因数マップを取得
        map<int, int> child_map = dfs(v, u);

        // Small-to-Large Merging: 常に大きいマップに小さいマップをマージする
        if (child_map.size() > res_map.size()) {
            swap(child_map, res_map);
        }

        // マージ処理（各素数の指数の最大値をとる）
        for (auto const& [prime, exp] : child_map) {
            res_map[prime] = max(res_map[prime], exp);
        }
    }
    
    // 計算結果の素因数マップからLCMの値を復元
    ll current_lcm = 1;
    for (auto const& [prime, exp] : res_map) {
        current_lcm = (current_lcm * power(prime, exp)) % MOD;
    }
    ans[u] = current_lcm;

    return res_map;
}


int main() {
    // 高速な入出力
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // 入力
    cin >> N;
    A.resize(N + 1);
    factors.resize(N + 1);
    adj.resize(N + 1);
    ans.resize(N + 1);

    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
    }
    
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // --- 前処理 ---
    // 1. エラトステネスの篩
    sieve(MAX_A - 1);
    // 2. 全ての重みを素因数分解
    for(int i = 1; i <= N; ++i) {
        factors[i] = factorize(A[i]);
    }

    // --- 計算 ---
    // 問題文より根は1で固定。親は存在しない0とする。
    dfs(1, 0);

    // --- 出力 ---
    for (int i = 1; i <= N; ++i) {
        cout << ans[i] << "\n";
    }

    return 0;
}
0