結果

問題 No.3250 最小公倍数
ユーザー yukicoder
提出日時 2025-08-05 22:19:05
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 860 ms / 2,000 ms
コード長 5,599 bytes
コンパイル時間 1,461 ms
コンパイル使用メモリ 122,276 KB
実行使用メモリ 75,408 KB
最終ジャッジ日時 2025-08-29 20:51:35
合計ジャッジ時間 11,020 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

// by gemini 2.5 pro
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

// FactorPair: {素因数, 指数} のペア
using FactorPair = std::pair<int, int>;
// FactorVec: FactorPairのソート済みベクター
using FactorVec = std::vector<FactorPair>;
using ll = long long;

// --- グローバル変数 ---
// 問題で指定された剰余
const int MOD = 998244353;
// a_i の最大値 + 5 (制約に合わせて10^6をカバー)
const int MAX_A = 1000005;

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

int N;
std::vector<int> A;
std::vector<std::vector<int>> adj;
std::vector<FactorVec> factors; // 各頂点の重みの素因数分解結果
std::vector<ll> ans; // 各頂点を根とする部分木のLCMの計算結果

// --- 関数定義 ---

/**
 * @brief エラトステネスの篩を用いて、nまでの各数の最小素因数を求める
 * @param n 上限値
 */
void sieve(int n) {
    min_prime.assign(n + 1, 0);
    std::iota(min_prime.begin(), min_prime.end(), 0); // min_prime[i] = i で初期化

    for (ll i = 2; i <= n; ++i) {
        if (min_prime[i] == i) { // iが素数
            for (ll j = i * i; j <= n; j += i) {
                if (min_prime[j] == j) { // まだ最小素因数が更新されていない場合
                    min_prime[j] = i;
                }
            }
        }
    }
}

/**
 * @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;
}

/**
 * @brief 前処理したテーブルを使い、数nを高速に素因数分解する
 * @param n 素因数分解する数
 * @return FactorVec (ソート済みの {素因数, 指数} のベクター)
 */
FactorVec factorize(int n) {
    FactorVec result_factors;
    if (n <= 1) return result_factors;

    while (n > 1) {
        int p = min_prime[n];
        int count = 0;
        while (n > 1 && min_prime[n] == p) {
            count++;
            n /= p;
        }
        result_factors.push_back({p, count});
    }
    return result_factors;
}

/**
 * @brief DFSで部分木のLCMを計算する (Small-to-Large Merging + vector)
 * @param u 現在の頂点
 * @param p 親の頂点
 * @return 頂点uの部分木のLCMの素因数分解ベクター
 */
FactorVec dfs(int u, int p) {
    // 1. まず自分自身の重みの素因数で結果ベクターを初期化
    FactorVec res_vec = factors[u];

    // 2. 各子について再帰的にDFSを実行
    for (int v : adj[u]) {
        if (v == p) continue;
        
        FactorVec child_vec = dfs(v, u);

        // 3. Small-to-Large Merging: 常に大きいベクターに小さいベクターをマージする
        // これにより、要素のコピー回数が全体でO(N log N)に抑えられる
        if (child_vec.size() > res_vec.size()) {
            std::swap(child_vec, res_vec);
        }
        
        // child_vecが空ならマージ不要
        if (child_vec.empty()) continue;

        // 4. マージ処理: 2つのソート済みベクターを線形時間でマージする
        FactorVec merged_vec;
        // 予めメモリを確保しておくと効率的
        merged_vec.reserve(res_vec.size() + child_vec.size());
        
        auto it1 = res_vec.begin();
        auto it2 = child_vec.begin();

        while (it1 != res_vec.end() && it2 != child_vec.end()) {
            if (it1->first < it2->first) {
                merged_vec.push_back(*it1++);
            } else if (it1->first > it2->first) {
                merged_vec.push_back(*it2++);
            } else { // 同じ素因数の場合、指数の大きい方を採用
                merged_vec.push_back({it1->first, std::max(it1->second, it2->second)});
                it1++;
                it2++;
            }
        }
        // 残った要素を追加
        merged_vec.insert(merged_vec.end(), it1, res_vec.end());
        merged_vec.insert(merged_vec.end(), it2, child_vec.end());
        
        // マージ結果をres_vecにムーブ代入
        res_vec = std::move(merged_vec);
    }
    
    // 5. 計算結果の素因数ベクターからLCMの値を復元
    ll current_lcm = 1;
    for (const auto& [prime, exp] : res_vec) {
        current_lcm = (current_lcm * power(prime, exp)) % MOD;
    }
    ans[u] = current_lcm;

    return res_vec;
}

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

    // --- 入力 ---
    std::cin >> N;
    
    // --- グローバル変数のサイズ確保 (RE回避のため必須) ---
    A.resize(N + 1);
    factors.resize(N + 1);
    adj.resize(N + 1);
    ans.resize(N + 1);

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

    // --- 計算 ---
    // 根である頂点1からDFSを開始 (親は存在しないので0とする)
    dfs(1, 0);

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

    return 0;
}
0