Submission #73319322

---

Source Code Expand

use proconio::input;
use std::collections::HashMap;

const MOD: u64 = 998244353;
const MAX_A: usize = 10_000_000;

static mut SPF: Vec<usize> = Vec::new();
static INIT: std::sync::Once = std::sync::Once::new();

fn init_spf() {
    unsafe {
        INIT.call_once(|| {
            let mut spf = vec![0; MAX_A + 1];
            let mut primes = Vec::with_capacity(664579);
            for i in 2..=MAX_A {
                if spf[i] == 0 {
                    spf[i] = i;
                    primes.push(i);
                }
                for &p in &primes {
                    let ip = i * p;
                    if ip > MAX_A {
                        break;
                    }
                    spf[ip] = p;
                    if p == spf[i] {
                        break;
                    }
                }
            }
            SPF = spf;
        });
    }
}

fn factorize(x: usize) -> Vec<(usize, u32)> {
    if x == 1 {
        return Vec::new();
    }
    unsafe {
        let mut factors = Vec::new();
        let mut n = x;
        while n > 1 {
            let p = SPF[n];
            let mut cnt = 0;
            while n % p == 0 {
                n /= p;
                cnt += 1;
            }
            factors.push((p, cnt));
        }
        factors
    }
}

fn mod_pow(mut base: u64, mut exp: u32, modulo: u64) -> u64 {
    let mut result = 1;
    base %= modulo;
    while exp > 0 {
        if exp & 1 == 1 {
            result = (result * base) % modulo;
        }
        base = (base * base) % modulo;
        exp >>= 1;
    }
    result
}

fn mod_inv(a: u64, modulo: u64) -> u64 {
    mod_pow(a, modulo as u32 - 2, modulo)
}

fn main() {
    init_spf();
    input! {
        t: usize,
    }
    for _ in 0..t {
        input! {
            n: usize,
            a: [usize; n],
        }

        let mut factors = Vec::with_capacity(n);
        let mut prime_exponents: HashMap<usize, Vec<u32>> = HashMap::new();

        for &x in &a {
            let f = factorize(x);
            for &(p, e) in &f {
                prime_exponents.entry(p).or_default().push(e);
            }
            factors.push(f);
        }

        let mut max1 = HashMap::new();
        let mut max2 = HashMap::new();
        let mut cnt_max = HashMap::new();

        for (&p, exponents) in &prime_exponents {
            let mut sorted = exponents.clone();
            sorted.sort_unstable_by(|a, b| b.cmp(a));
            let m1 = sorted[0];
            let c1 = sorted.iter().take_while(|&&x| x == m1).count() as u32;
            let m2 = if sorted.len() > 1 && sorted[1] < m1 {
                sorted[1]
            } else {
                0
            };
            max1.insert(p, m1);
            cnt_max.insert(p, c1);
            max2.insert(p, m2);
        }

        let mut total_lcm = 1u64;
        for (&p, &exp) in &max1 {
            total_lcm = (total_lcm * mod_pow(p as u64, exp, MOD)) % MOD;
        }

        let mut answers = Vec::with_capacity(n);
        for k in 0..n {
            let mut res = total_lcm;
            for &(p, e) in &factors[k] {
                if e == max1[&p] && cnt_max[&p] == 1 {
                    let old_power = mod_pow(p as u64, max1[&p], MOD);
                    let new_power = mod_pow(p as u64, max2[&p], MOD);
                    let inv_old = mod_inv(old_power, MOD);
                    res = (res * inv_old) % MOD;
                    res = (res * new_power) % MOD;
                }
            }
            answers.push(res);
        }

        println!("{}", answers.iter().map(|x| x.to_string()).collect::<Vec<_>>().join(" "));
    }
}

Submission Info

Judge Result