#856598 (Rust) No.458 異なる素数の和

• 問題: No.458 異なる素数の和
• ユーザー: ngtkana
• 提出日時: 2023-04-05 21:49:58
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 70 ms / 2,000 ms
• コード長: 15,536 bytes
• コンパイル時間: 1,669 ms
• コンパイル使用メモリ: 179,080 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-04-10 01:33:37
• 合計ジャッジ時間: 3,236 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,812 KB
testcase_01	AC	21 ms; 6,940 KB
testcase_02	AC	27 ms; 6,944 KB
testcase_03	AC	5 ms; 6,944 KB
testcase_04	AC	6 ms; 6,940 KB
testcase_05	AC	56 ms; 6,940 KB
testcase_06	AC	25 ms; 6,940 KB
testcase_07	AC	1 ms; 6,944 KB
testcase_08	AC	57 ms; 6,944 KB
testcase_09	AC	3 ms; 6,940 KB
testcase_10	AC	0 ms; 6,944 KB
testcase_11	AC	70 ms; 6,944 KB
testcase_12	AC	1 ms; 6,940 KB
testcase_13	AC	1 ms; 6,944 KB
testcase_14	AC	1 ms; 6,940 KB
testcase_15	AC	1 ms; 6,940 KB
testcase_16	AC	3 ms; 6,944 KB
testcase_17	AC	1 ms; 6,944 KB
testcase_18	AC	0 ms; 6,940 KB
testcase_19	AC	1 ms; 6,944 KB
testcase_20	AC	1 ms; 6,940 KB
testcase_21	AC	1 ms; 6,944 KB
testcase_22	AC	1 ms; 6,940 KB
testcase_23	AC	1 ms; 6,940 KB
testcase_24	AC	1 ms; 6,944 KB
testcase_25	AC	1 ms; 6,944 KB
testcase_26	AC	1 ms; 6,940 KB
testcase_27	AC	23 ms; 6,940 KB
testcase_28	AC	67 ms; 6,944 KB
testcase_29	AC	2 ms; 6,940 KB
testcase_30	AC	15 ms; 6,944 KB

コンパイルメッセージ

warning: unused imports: `PrimeNumbers`, `lpd_sieve::LpdSieve`
   --> main.rs:458:9
    |
458 |         lpd_sieve::LpdSieve,
    |         ^^^^^^^^^^^^^^^^^^^
459 |         sieve::Sieve,
460 |         sieve_base::{PrimeFactorsByLookup, PrimeFactorsByTrialDivision, PrimeNumbers},
    |                                                                         ^^^^^^^^^^^^
    |
    = note: `#[warn(unused_imports)]` on by default

warning: 1 warning emitted

ソースコード

use erato::Sieve;
use std::io::{stdin, BufRead};

fn main() {
    let stdin = stdin();
    let mut stdin = stdin.lock().lines().map(Result::unwrap);
    let n = stdin.next().unwrap().parse::<usize>().unwrap();
    let mut dp = vec![None::<isize>; n + 1];
    dp[0] = Some(0);
    for p in Sieve::new()
        .prime_numbers::<usize>()
        .take_while(|&p| p <= n)
    {
        for i in (0..=n - p).rev() {
            change_max!(&mut dp[i + p], dp[i].map(|x| x + 1));
        }
    }
    let ans = dp[n].unwrap_or(-1);
    println!("{}", ans);
}

#[macro_export]
macro_rules! change_max {
    ($target:expr, $src:expr) => {
        let src = $src;
        let target = $target;
        $crate::ordtools::Ordtools::change_max(target, src);
    };
}

// erato {{{
#[allow(dead_code)]
mod erato {
    mod converters {
        use {
            super::{Int, PrimeFactorsByLookup, PrimeFactorsByTrialDivision},
            std::{iter::Peekable, 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,
            ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Rem, RemAssign, Sub, 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, PrimeNumbers},
            sieve_kind, Int, 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, PrimeNumbers},
            sieve_kind, Int, 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::{self, SieveKind},
                Int, PrimeFactors, Rle, Unique,
            },
            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
        }
    }
    use sieve_base::SieveBase;
    pub use {
        converters::{PrimeFactors, Rle, Unique},
        int::Int,
        lpd_sieve::LpdSieve,
        sieve::Sieve,
        sieve_base::{PrimeFactorsByLookup, PrimeFactorsByTrialDivision, PrimeNumbers},
    };
}
// }}}
// ordtools {{{
#[allow(dead_code)]
mod ordtools {
    pub trait Ordtools: PartialOrd + Sized {
        fn change_min(&mut self, mut rhs: Self) {
            if self > &mut rhs {
                *self = rhs;
            }
        }
        fn change_max(&mut self, mut rhs: Self) {
            if self < &mut rhs {
                *self = rhs;
            }
        }
    }
    impl<T: PartialOrd + Sized> Ordtools for T {}
}
// }}}