提出 #62781239

---

ソースコード 拡げる

use erato::Sieve;
use itertools::Itertools;
use proconio::input;

fn main() {
    input! {
        n: usize,
        k: usize,
        a: [usize; n],
    }
    let lim = a.iter().copied().max().unwrap() + 1;
    let mut sieve = Sieve::with_len(lim);
    let mut count = vec![0; lim];
    for &x in &a {
        count[x] += 1;
    }
    for p in sieve.prime_numbers::<usize>().take_while(|&p| p < lim) {
        for i in (1..=(lim - 1) / p).rev() {
            count[i] += count[i * p];
        }
    }
    let mut ans = (0..lim)
        .map(|i| if count[i] >= k { i } else { 0 })
        .collect_vec();
    for p in sieve.prime_numbers::<usize>().take_while(|&p| p < lim) {
        for i in 1..=(lim - 1) / p {
            ans[i * p] = ans[i].max(ans[i * p]);
        }
    }
    for &x in &a {
        let ans = ans[x];
        println!("{ans}");
    }
}

// erato {{{
// https://ngtkana.github.io/ac-adapter-rs/erato/index.html

#[allow(dead_code)]
mod erato {
    mod converters {
        use super::Int;
        use super::PrimeFactorsByLookup;
        use super::PrimeFactorsByTrialDivision;
        use std::iter::Peekable;
        use std::marker::PhantomData;
        pub trait PrimeFactors<T: Int>: Sized + Iterator<Item = T> {
            fn unique(self) -> Unique<T, Self> {
                Unique {
                    iter: self,
                    prev: None,
                }
            }
            fn rle(self) -> Rle<T, Self> {
                Rle {
                    iter: self.peekable(),
                    _marker: PhantomData,
                }
            }
        }
        impl<'a, T: Int> PrimeFactors<T> for PrimeFactorsByTrialDivision<'a, T> {}
        impl<'a, T: Int> PrimeFactors<T> for PrimeFactorsByLookup<'a, T> {}
        pub struct Unique<T: Int, P: PrimeFactors<T>> {
            iter: P,
            prev: Option<T>,
        }
        impl<T: Int, P: PrimeFactors<T>> Iterator for Unique<T, P> {
            type Item = P::Item;
            fn next(&mut self) -> Option<Self::Item> {
                let prev = self.prev;
                let res = self.iter.find(|&p| Some(p) != prev);
                self.prev = res;
                res
            }
        }
        pub struct Rle<T: Int, P: PrimeFactors<T>> {
            iter: Peekable<P>,
            _marker: PhantomData<T>,
        }
        impl<T: Int, P: PrimeFactors<T>> Iterator for Rle<T, P> {
            type Item = (P::Item, usize);
            fn next(&mut self) -> Option<Self::Item> {
                if let Some(p) = self.iter.next() {
                    let mut multi = 1;
                    while self.iter.peek() == Some(&p) {
                        multi += 1;
                        self.iter.next();
                    }
                    Some((p, multi))
                } else {
                    None
                }
            }
        }
    }
    mod int {
        use std::fmt::Debug;
        use std::ops::Add;
        use std::ops::AddAssign;
        use std::ops::Div;
        use std::ops::DivAssign;
        use std::ops::Mul;
        use std::ops::MulAssign;
        use std::ops::Rem;
        use std::ops::RemAssign;
        use std::ops::Sub;
        use std::ops::SubAssign;
        pub trait Int:
            Debug
            + Copy
            + Ord
            + Add<Output = Self>
            + AddAssign
            + Sub<Output = Self>
            + SubAssign
            + Mul<Output = Self>
            + MulAssign
            + Div<Output = Self>
            + DivAssign
            + Rem<Output = Self>
            + RemAssign
        {
            fn zero() -> Self;
            fn one() -> Self;
            fn two() -> Self;
            fn as_usize(self) -> usize;
            fn from_usize(src: usize) -> Self;
        }
        macro_rules! impl_int {
            ($($t:ty),* $(,)?) => {$(
                impl Int for $t {
                    fn zero() -> Self {
                        0
                    }
                    fn one() -> Self {
                        1
                    }
                    fn two() -> Self {
                        2
                    }
                    fn as_usize(self) -> usize {
                        self as usize
                    }
                    fn from_usize(src: usize) -> Self {
                        src as Self
                    }
                }
            )*}
        }
        impl_int! {
            usize, u8, u16, u32, u64, u128,
            isize, i8, i16, i32, i64, i128,
        }
    }
    mod lpd_sieve {
        use super::sieve_base::PrimeFactorsByLookup;
        use super::sieve_base::PrimeNumbers;
        use super::sieve_kind;
        use super::Int;
        use super::SieveBase;
        #[derive(Default, Debug, Clone, PartialEq)]
        pub struct LpdSieve {
            base: SieveBase<sieve_kind::Usize>,
        }
        impl LpdSieve {
            pub fn new() -> Self {
                Self {
                    base: SieveBase::new(),
                }
            }
            pub fn is_empty(&self) -> bool {
                self.base.is_empty()
            }
            pub fn len(&self) -> usize {
                self.base.len()
            }
            pub fn with_len(n: usize) -> Self {
                Self {
                    base: SieveBase::with_len(n),
                }
            }
            pub fn is_prime<T: Int>(&mut self, x: T) -> bool {
                self.base.is_prime(x)
            }
            pub fn lpd<T: Int>(&mut self, x: T) -> T {
                self.base.lpd(x)
            }
            pub fn prime_numbers<T: Int>(&mut self) -> PrimeNumbers<sieve_kind::Usize, T> {
                self.base.prime_numbers()
            }
            pub fn prime_factors<T: Int>(&mut self, n: T) -> PrimeFactorsByLookup<T> {
                self.base.prime_factors_by_lookup(n)
            }
        }
    }
    mod sieve {
        use super::sieve_base::PrimeFactorsByTrialDivision;
        use super::sieve_base::PrimeNumbers;
        use super::sieve_kind;
        use super::Int;
        use super::SieveBase;
        #[derive(Default, Debug, Clone, PartialEq)]
        pub struct Sieve {
            base: SieveBase<sieve_kind::Boolean>,
        }
        impl Sieve {
            pub fn new() -> Self {
                Self {
                    base: SieveBase::new(),
                }
            }
            pub fn is_empty(&self) -> bool {
                self.base.is_empty()
            }
            pub fn len(&self) -> usize {
                self.base.len()
            }
            pub fn with_len(n: usize) -> Self {
                Self {
                    base: SieveBase::with_len(n),
                }
            }
            pub fn is_prime<T: Int>(&mut self, x: T) -> bool {
                self.base.is_prime(x)
            }
            pub fn prime_numbers<T: Int>(&mut self) -> PrimeNumbers<sieve_kind::Boolean, T> {
                self.base.prime_numbers()
            }
            pub fn prime_factors<T: Int>(&mut self, n: T) -> PrimeFactorsByTrialDivision<T> {
                self.base.prime_factors_by_trial_division(n)
            }
        }
    }
    mod sieve_base {
        use super::sieve_kind::SieveKind;
        use super::sieve_kind::{self};
        use super::Int;
        use super::PrimeFactors;
        use super::Rle;
        use super::Unique;
        use std::marker::PhantomData;
        #[derive(Debug, Clone, PartialEq)]
        pub struct SieveBase<S: SieveKind> {
            sieve: Vec<S::SieveValue>,
            list: Vec<usize>,
        }
        impl<S: SieveKind> SieveBase<S> {
            pub fn new() -> Self {
                Self {
                    sieve: S::new(),
                    list: Vec::new(),
                }
            }
            pub fn is_empty(&self) -> bool {
                self.sieve.is_empty()
            }
            pub fn len(&self) -> usize {
                self.sieve.len()
            }
            pub fn with_len(n: usize) -> Self {
                let sieve = S::construct(n);
                let list = sieve
                    .iter()
                    .enumerate()
                    .filter(|&(index, &b)| S::is_prime(index, b))
                    .map(|(index, _)| index)
                    .collect();
                Self { sieve, list }
            }
            pub fn is_prime<T: Int>(&mut self, x: T) -> bool {
                assert!(T::zero() <= x);
                let x = x.as_usize();
                if self.sieve.len() <= x {
                    *self = Self::with_len(x + 1);
                }
                S::is_prime(x, self.sieve[x.as_usize()])
            }
            pub fn prime_numbers<T: Int>(&mut self) -> PrimeNumbers<S, T> {
                PrimeNumbers {
                    sieve: self,
                    index: 0,
                    _marker: PhantomData,
                }
            }
            fn extend(&mut self, len: usize) {
                assert!(2 * self.len() <= len);
                *self = Self::with_len(len);
            }
        }
        impl<S: SieveKind> Default for SieveBase<S> {
            fn default() -> Self {
                Self::new()
            }
        }
        impl SieveBase<sieve_kind::Boolean> {
            pub fn prime_factors_by_trial_division<T: Int>(
                &mut self,
                n: T,
            ) -> PrimeFactorsByTrialDivision<T> {
                assert!(T::zero() < n);
                let mut prime_numbers = self.prime_numbers();
                PrimeFactorsByTrialDivision {
                    p: prime_numbers.next().unwrap(),
                    prime_numbers,
                    n,
                }
            }
        }
        pub struct PrimeNumbers<'a, S: SieveKind, T: Int> {
            sieve: &'a mut SieveBase<S>,
            index: usize,
            _marker: PhantomData<T>,
        }
        pub struct PrimeFactorsByTrialDivision<'a, T: Int> {
            prime_numbers: PrimeNumbers<'a, sieve_kind::Boolean, T>,
            p: T,
            n: T,
        }
        impl<'a, S: SieveKind, T: Int> Iterator for PrimeNumbers<'a, S, T> {
            type Item = T;
            fn next(&mut self) -> Option<Self::Item> {
                let Self { sieve, index, .. } = self;
                let p = if let Some(&p) = sieve.list.get(*index) {
                    T::from_usize(p)
                } else {
                    sieve.extend((sieve.len() * 2).max(3));
                    T::from_usize(sieve.list[*index])
                };
                *index += 1;
                Some(p)
            }
        }
        impl<T: Int> PrimeFactorsByTrialDivision<'_, T> {
            pub fn unique(self) -> Unique<T, Self> {
                PrimeFactors::unique(self)
            }
            pub fn rle(self) -> Rle<T, Self> {
                PrimeFactors::rle(self)
            }
        }
        impl<'a, T: Int> Iterator for PrimeFactorsByTrialDivision<'a, T> {
            type Item = T;
            fn next(&mut self) -> Option<Self::Item> {
                let Self {
                    prime_numbers,
                    p,
                    n,
                } = self;
                if *n == T::one() {
                    None
                } else {
                    while *n % *p != T::zero() {
                        if *n <= *p * *p {
                            *p = *n;
                            break;
                        }
                        *p = prime_numbers.next().unwrap();
                    }
                    *n /= *p;
                    Some(*p)
                }
            }
        }
        pub struct PrimeFactorsByLookup<'a, T: Int> {
            sieve: &'a mut SieveBase<sieve_kind::Usize>,
            n: T,
        }
        impl SieveBase<sieve_kind::Usize> {
            pub fn prime_factors_by_lookup<T: Int>(&mut self, n: T) -> PrimeFactorsByLookup<T> {
                assert!(T::zero() < n);
                PrimeFactorsByLookup { sieve: self, n }
            }
            pub fn lpd<T: Int>(&mut self, n: T) -> T {
                let n = n.as_usize();
                if self.sieve.len() <= n {
                    self.extend(2 * (n + 1));
                }
                T::from_usize(self.sieve[n])
            }
        }
        impl<T: Int> PrimeFactorsByLookup<'_, T> {
            pub fn unique(self) -> Unique<T, Self> {
                PrimeFactors::unique(self)
            }
            pub fn rle(self) -> Rle<T, Self> {
                PrimeFactors::rle(self)
            }
        }
        impl<'a, T: Int> Iterator for PrimeFactorsByLookup<'a, T> {
            type Item = T;
            fn next(&mut self) -> Option<Self::Item> {
                let Self { sieve, n } = self;
                if *n == T::one() {
                    None
                } else {
                    let p = sieve.lpd(*n);
                    *n /= p;
                    Some(p)
                }
            }
        }
    }
    mod sieve_kind {
        pub trait SieveKind {
            type SieveValue: Copy;
            fn new() -> Vec<Self::SieveValue>;
            fn construct(len: usize) -> Vec<Self::SieveValue>;
            fn is_prime(index: usize, b: Self::SieveValue) -> bool;
        }
        #[derive(Debug, Clone, Copy, PartialEq, Eq)]
        pub enum Boolean {}
        #[derive(Debug, Clone, Copy, PartialEq, Eq)]
        pub enum Usize {}
        impl SieveKind for Boolean {
            type SieveValue = bool;
            fn new() -> Vec<Self::SieveValue> {
                Vec::new()
            }
            fn construct(len: usize) -> Vec<Self::SieveValue> {
                construct_is_prime_table(len)
            }
            fn is_prime(_index: usize, b: Self::SieveValue) -> bool {
                b
            }
        }
        impl SieveKind for Usize {
            type SieveValue = usize;
            fn new() -> Vec<Self::SieveValue> {
                Vec::new()
            }
            fn construct(len: usize) -> Vec<Self::SieveValue> {
                construct_lpd_table(len)
            }
            fn is_prime(index: usize, b: Self::SieveValue) -> bool {
                index == b
            }
        }
        pub fn construct_is_prime_table(n: usize) -> Vec<bool> {
            let mut is_prime = vec![true; n];
            (0..2.min(n)).for_each(|i| is_prime[i] = false);
            for p in (2..).take_while(|&p| p * p < n) {
                if !is_prime[p] {
                    continue;
                }
                let mut i = p * p;
                while i < n {
                    is_prime[i] = false;
                    i += p;
                }
            }
            is_prime
        }
        fn construct_lpd_table(n: usize) -> Vec<usize> {
            let mut lpd = vec![std::usize::MAX; n];
            for p in 2..n {
                if lpd[p] != std::usize::MAX {
                    continue;
                }
                lpd[p] = p;
                let mut i = p * p;
                while i < n {
                    if lpd[i] == std::usize::MAX {
                        lpd[i] = p;
                    }
                    i += p;
                }
            }
            lpd
        }
    }
    pub use converters::PrimeFactors;
    pub use converters::Rle;
    pub use converters::Unique;
    pub use int::Int;
    pub use lpd_sieve::LpdSieve;
    pub use sieve::Sieve;
    pub use sieve_base::PrimeFactorsByLookup;
    pub use sieve_base::PrimeFactorsByTrialDivision;
    pub use sieve_base::PrimeNumbers;
    use sieve_base::SieveBase;
}
// }}}

提出情報

ジャッジ結果