結果

問題 No.3250 最小公倍数
コンテスト
ユーザー titia
提出日時 2026-06-21 06:14:22
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 1,104 ms / 2,000 ms
コード長 3,296 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,294 ms
コンパイル使用メモリ 200,428 KB
実行使用メモリ 154,784 KB
最終ジャッジ日時 2026-06-21 06:14:40
合計ジャッジ時間 15,220 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use std::collections::HashMap;
use std::io::{self, Read};

const MAX: usize = 1_000_010;
const MOD: i64 = 998_244_353;

fn mod_pow(mut a: i64, mut e: usize) -> i64 {
    let mut res = 1i64;

    while e > 0 {
        if e & 1 == 1 {
            res = res * a % MOD;
        }
        a = a * a % MOD;
        e >>= 1;
    }

    res
}

fn fact(mut x: usize, sieve: &[usize]) -> HashMap<usize, usize> {
    let mut mp = HashMap::new();

    while x != 1 {
        let p = sieve[x];
        *mp.entry(p).or_insert(0) += 1;
        x /= p;
    }

    mp
}

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let mut it = input.split_whitespace();

    let n: usize = it.next().unwrap().parse().unwrap();

    let mut a = vec![0usize; n];
    for i in 0..n {
        a[i] = it.next().unwrap().parse().unwrap();
    }

    // smallest prime factor
    let mut sieve = vec![0usize; MAX];
    for i in 0..MAX {
        sieve[i] = i;
    }

    for i in 2..MAX {
        if sieve[i] != i {
            continue;
        }

        let mut j = i;
        while j < MAX {
            if sieve[j] == j {
                sieve[j] = i;
            }
            j += i;
        }
    }

    let mut e = vec![Vec::<usize>::new(); n];

    for _ in 0..n - 1 {
        let x: usize = it.next().unwrap().parse::<usize>().unwrap() - 1;
        let y: usize = it.next().unwrap().parse::<usize>().unwrap() - 1;

        e[x].push(y);
        e[y].push(x);
    }

    // rooted tree
    let root = 0;

    let mut parent = vec![usize::MAX; n];
    parent[root] = root;

    let mut child = vec![Vec::<usize>::new(); n];

    let mut stack = vec![root];
    let mut topo = Vec::new();

    while let Some(v) = stack.pop() {
        topo.push(v);

        for &to in &e[v] {
            if parent[to] == usize::MAX {
                parent[to] = v;
                child[v].push(to);
                stack.push(to);
            }
        }
    }

    let mut dp: Vec<Option<(i64, HashMap<usize, usize>)>> =
        (0..n).map(|_| None).collect();

    let mut ans = vec![0i64; n];

    for &v in topo.iter().rev() {
        let mut score = a[v] as i64 % MOD;
        let mut mp = fact(a[v], &sieve);

        for &to in &child[v] {
            let (child_score, mut child_map) =
                dp[to].take().unwrap();

            // small-to-large
            if mp.len() < child_map.len() {
                std::mem::swap(&mut mp, &mut child_map);
                score = child_score;
            }

            for (p, cnt2) in child_map {
                match mp.get_mut(&p) {
                    Some(cnt1) => {
                        if *cnt1 < cnt2 {
                            let add = cnt2 - *cnt1;
                            score =
                                score * mod_pow(p as i64, add) % MOD;
                            *cnt1 = cnt2;
                        }
                    }
                    None => {
                        mp.insert(p, cnt2);
                        score =
                            score * mod_pow(p as i64, cnt2) % MOD;
                    }
                }
            }
        }

        ans[v] = score;
        dp[v] = Some((score, mp));
    }

    for x in ans {
        println!("{}", x);
    }
}
0