AtCoder Beginner Contest 445 E

https://atcoder.jp/contests/abc445/tasks/abc445_e

LCMの各素数の個数を保持しておくと、Aの要素を除いたときにその要素の素数の個数がLCMより小さければその素数はに関してLCMは変化なしです。ただし、個数が同じならどうすればいいかわかりません。そのときのためにAの中で2位の個数まで保持しておきます。

// Many LCMs
#![allow(non_snake_case)]

use std::collections::HashMap;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

// ax = by + 1 (a, b > 0)
fn linear_diophantine(a: i64, b: i64) -> Option<(i64, i64)> {
    if a == 1 {
        return Some((1, 0))
    }
    
    let q = b / a;
    let r = b % a;
    if r == 0 {
        return None
    }
    let (x1, y1) = linear_diophantine(r, a)?;
    Some((-q * x1 - y1, -x1))
}

fn inverse(a: i64, d: i64) -> i64 {
    let (x, _y) = linear_diophantine(a, d).unwrap();
    if x >= 0 {
        x % d
    }
    else {
        x % d + d
    }
}

fn div_pow(n: i64, d: i64) -> (u32, i64) {
    let mut e: u32 = 0;
    let mut m = n;
    while m % d == 0 {
        e += 1;
        m /= d
    }
    (e, m)
}


//////////////////// Factors ////////////////////

type Factors = Vec<(i64, u32)>;
fn make_min_prime_table(N: usize) -> Vec<i64> {
    let mut a: Vec<i64> = (0..(N as i64)+1).collect();
    for p in (2..).take_while(|&p| p*p <= N) {
        if a[p] != p as i64 {   // not prime
            continue
        }
        for n in (p*2..N+1).step_by(p) {
            if a[n] == n as i64 {
                a[n] = p as i64
            }
        }
    }
    a
}

fn factorize(mut n: i64, table: &Vec<i64>) -> Factors {
    if n == 1 {
        return vec![]
    }
    
    let mut fs: Vec<(i64, u32)> = vec![];
    while n != 1 {
        let p = table[n as usize];
        let (e, m) = div_pow(n, p);
        fs.push((p, e));
        n = m
    }
    fs
}


//////////////////// process ////////////////////

fn read_case() -> Vec<i64> {
    let _N: usize = read();
    let A: Vec<i64> = read_vec();
    A
}

const D: i64 = 998244353;

fn F_each(A: Vec<i64>, table: &Vec<i64>) {
    let N = A.len();
    let fss: Vec<Factors> = A.iter().map(|&n| factorize(n, &table)).collect();
    let mut m: HashMap<i64, [u32; 2]> = HashMap::new();
    for fs in fss.iter() {
        for &(p, e) in fs.iter() {
            let en = m.entry(p).or_insert([0; 2]);
            if e > en[0] {
                en[1] = en[0];
                en[0] = e;
            }
            else if e > en[1] {
                en[1] = e
            }
        }
    }
    
    let lcm = m.iter().fold(1, |x, (&p, es)| x*p.pow(es[0])%D);
    let mut lcms: Vec<i64> = vec![0; N];
    for (i, fs) in fss.iter().enumerate() {
        let mut div: i64 = 1;
        for &(p, e) in fs.iter() {
            let es = m.get(&p).unwrap();
            if es[0] == e {
                div = div * p.pow(e-es[1]) % D
            }
        }
        lcms[i] = lcm * inverse(div, D) % D;
    }
    
    println!("{}", lcms.iter().map(|n| n.to_string()).
                            collect::<Vec<String>>().join(" "))
}

fn F(T: usize) {
    let table = make_min_prime_table(10_000_000);
    for _ in 0..T {
        let A = read_case();
        F_each(A, &table)
    }
}

fn main() {
    let T: usize = read();
    F(T)
}