結果
| 問題 |
No.458 異なる素数の和
|
| コンテスト | |
| ユーザー |
 ngtkana
|
| 提出日時 | 2023-04-05 21:49:58 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 73 ms / 2,000 ms |
| コード長 | 15,536 bytes |
| コンパイル時間 | 13,953 ms |
| コンパイル使用メモリ | 384,832 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-10-02 02:49:34 |
| 合計ジャッジ時間 | 15,656 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 28 |
コンパイルメッセージ
warning: unused imports: `PrimeNumbers`, `lpd_sieve::LpdSieve`
--> src/main.rs:458:9
|
458 | lpd_sieve::LpdSieve,
| ^^^^^^^^^^^^^^^^^^^
459 | sieve::Sieve,
460 | sieve_base::{PrimeFactorsByLookup, PrimeFactorsByTrialDivision, PrimeNumbers},
| ^^^^^^^^^^^^
|
= note: `#[warn(unused_imports)]` on by default
ソースコード
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 {}
}
// }}}