結果

問題 No.3127 Multiple of Twin Prime
ユーザー 37kt
提出日時 2025-05-08 13:53:07
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 37 ms / 2,500 ms
コード長 9,161 bytes
コンパイル時間 12,540 ms
コンパイル使用メモリ 387,864 KB
実行使用メモリ 11,140 KB
最終ジャッジ日時 2025-05-08 13:53:24
合計ジャッジ時間 15,506 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

pub use __cargo_equip::prelude::*;

use eratosthenes::Eratosthenes;
#[allow(unused_imports)]
use proconio::{
    fastout, input,
    marker::{Bytes, Chars, Usize1},
};

#[fastout]
fn main() {
    let sieve = Eratosthenes::new(10_000_002);
    let primes = sieve.primes().collect::<Vec<_>>();
    let a = primes
        .windows(2)
        .filter_map(|p| (p[0] + 2 == p[1]).then_some(p[0] * p[1]))
        .collect::<Vec<_>>();
    input! {
        t: usize,
    }
    for _ in 0..t {
        input! {
            n: usize,
        }
        let i = a.partition_point(|&p| p <= n);
        if i == 0 {
            println!("-1");
        } else {
            println!("{}", a[i - 1]);
        }
    }
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `path+file:///comp_rust/cprs/crates/algebra/numeric_traits#0.1.0`     published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::numeric_traits`
///  - `path+file:///comp_rust/cprs/crates/number_theory/eratosthenes#0.1.0` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::eratosthenes`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod numeric_traits {pub mod inf{pub trait Inf:PartialOrd{fn inf()->Self;}pub trait NegInf:PartialOrd{fn neg_inf()->Self;}macro_rules!impl_inf{($($t:ty,$inf:expr,)*)=>{$(impl Inf for$t{fn inf()->Self{$inf}})*}}macro_rules!impl_neg_inf{($($t:ty,$neg_inf:expr,)*)=>{$(impl NegInf for$t{fn neg_inf()->Self{$neg_inf}})*}}impl_inf!{i32,1_001_000_000,u32,1_001_000_000,f32,1e10,i64,4_004_000_000_000_000_000,isize,4_004_000_000_000_000_000,u64,4_004_000_000_000_000_000,usize,4_004_000_000_000_000_000,f64,1e20,i128,8_008_000_000_000_000_000_000_000_000_000_000_000,u128,8_008_000_000_000_000_000_000_000_000_000_000_000,}impl_neg_inf!{i32,-1_001_000_000,u32,0,f32,-1e10,i64,-4_004_000_000_000_000_000,isize,-4_004_000_000_000_000_000,u64,0,usize,0,f64,-1e20,i128,-8_008_000_000_000_000_000_000_000_000_000_000_000,u128,0,}}pub use inf::*;pub mod zero_one{use std::ops::{Add,Mul};pub trait Zero:Sized+Add<Output=Self>{fn zero()->Self;}pub trait One:Sized+Mul<Output=Self>{fn one()->Self;}macro_rules!impl_zero_one{($($t:ty),*)=>{$(impl Zero for$t{fn zero()->Self{0 as$t}}impl One for$t{fn one()->Self{1 as$t}})*}}impl_zero_one!(u8,u16,u32,u64,u128,usize,i8,i16,i32,i64,i128,isize,f32,f64);}pub use zero_one::*;pub mod cast{pub trait Cast<T>{fn cast(self)->T;}macro_rules!impl_cast_2{($t1:ty,$($t2:ty),*)=>{$(impl Cast<$t2>for$t1{fn cast(self)->$t2{self as$t2}})*}}macro_rules!impl_cast_1{($($t:ty),*)=>{$(impl_cast_2!{$t,u8,u16,u32,u64,u128,i8,i16,i32,i64,i128,usize,isize,f32,f64})*}}impl_cast_1!{u8,u16,u32,u64,u128,i8,i16,i32,i64,i128,usize,isize,f32,f64}}pub use cast::*;pub mod numeric{use std::ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Sub,SubAssign};use crate::__cargo_equip::crates::numeric_traits::zero_one;pub trait Numeric:Sized+Clone+Copy+std::fmt::Debug+std::fmt::Display+PartialEq+Add<Output=Self>+AddAssign+Sub<Output=Self>+SubAssign+Mul<Output=Self>+MulAssign+Div<Output=Self>+DivAssign+zero_one::Zero+zero_one::One{}macro_rules!impl_numeric{($($t:ty),*)=>{$(impl Numeric for$t{})*};}impl_numeric!{u8,u16,u32,u64,u128,i8,i16,i32,i64,i128,usize,isize,f32,f64}}pub use numeric::*;pub mod integer{use std::ops::{BitAnd,BitAndAssign,BitOr,BitOrAssign,BitXor,BitXorAssign,Rem,RemAssign,Shl,ShlAssign,Shr,ShrAssign,};use crate::__cargo_equip::crates::numeric_traits::Numeric;pub trait Integer:Numeric+Eq+Ord+std::hash::Hash+Rem<Output=Self>+RemAssign+BitXor<Output=Self>+BitXorAssign+BitAnd<Output=Self>+BitAndAssign+BitOr<Output=Self>+BitOrAssign+Shl<usize,Output=Self>+ShlAssign<usize>+Shr<usize,Output=Self>+ShrAssign<usize>{const MIN:Self;const MAX:Self;fn popcount(self)->usize;fn msb_index(self)->usize;fn lsb_index(self)->usize;fn msb(self)->Self;fn lsb(self)->Self;fn ceil_pow2(self)->Self;fn floor_pow2(self)->Self;fn ceil_log2(self)->usize;fn floor_log2(self)->usize;fn checked_msb_index(self)->Option<usize>;fn checked_lsb_index(self)->Option<usize>;fn checked_ceil_pow2(self)->Option<Self>;fn checked_floor_pow2(self)->Option<Self>;fn checked_ceil_log2(self)->Option<usize>;fn checked_floor_log2(self)->Option<usize>;fn floor_div(self,other:Self)->Self;fn ceil_div(self,other:Self)->Self;fn gcd(self,other:Self)->Self;fn lcm(self,other:Self)->Self;}macro_rules!impl_integer{($($t:ty),*)=>{$(impl Integer for$t{const MIN:Self=<$t>::MIN;const MAX:Self=<$t>::MAX;fn popcount(self)->usize{self.count_ones()as usize}fn msb_index(self)->usize{(<$t>::BITS-1-self.leading_zeros())as usize}fn lsb_index(self)->usize{self.trailing_zeros()as usize}fn msb(self)->Self{if self==0{0}else{1<<self.msb_index()}}fn lsb(self)->Self{self&self.wrapping_neg()}fn ceil_pow2(self)->Self{1<<self.ceil_log2()}fn floor_pow2(self)->Self{assert!(self>0);self.msb()}fn ceil_log2(self)->usize{assert!(self>0);(<$t>::BITS-(self-1).leading_zeros())as usize}fn floor_log2(self)->usize{assert!(self>0);self.msb_index()}fn checked_msb_index(self)->Option<usize>{if self==0{None}else{Some(self.msb_index())}}fn checked_lsb_index(self)->Option<usize>{if self==0{None}else{Some(self.lsb_index())}}fn checked_ceil_pow2(self)->Option<Self>{if self<=0{None}else{Some(self.ceil_pow2())}}fn checked_floor_pow2(self)->Option<Self>{if self<=0{None}else{Some(self.floor_pow2())}}fn checked_ceil_log2(self)->Option<usize>{if self<=0{None}else{Some(self.ceil_log2())}}fn checked_floor_log2(self)->Option<usize>{if self<=0{None}else{Some(self.floor_log2())}}#[allow(unused_comparisons)]fn floor_div(self,other:Self)->Self{self/other-if self^other<0&&self%other!=0{1}else{0}}#[allow(unused_comparisons)]fn ceil_div(self,other:Self)->Self{self/other+if self^other>=0&&self%other!=0{1}else{0}}#[allow(unused_comparisons)]fn gcd(self,other:Self)->Self{let mut x=if self<0{0-self}else{self};let mut y=if other<0{0-other}else{other};if x==0||y==0{return x|y;}let n=x.trailing_zeros();let m=y.trailing_zeros();x>>=n;y>>=m;while x!=y{if x>y{x-=y;x>>=x.trailing_zeros();}else{y-=x;y>>=y.trailing_zeros();}}x<<n.min(m)}fn lcm(self,other:Self)->Self{self/self.gcd(other)*other}})*};}impl_integer!{u8,u16,u32,u64,u128,i8,i16,i32,i64,i128,usize,isize}}pub use integer::*;pub mod signed{use std::ops::Neg;pub trait Signed:Sized+Neg<Output=Self>{fn signum(self)->Self;}macro_rules!impl_signed_integer{($($t:ty),*)=>{$(impl Signed for$t{fn signum(self)->Self{match self{n if n>0=>1,0=>0,_=>-1,}}})*};}macro_rules!impl_signed_float{($($t:ty),*)=>{$(impl Signed for$t{fn signum(self)->Self{if self.is_nan(){self}else if self==0.0{0.0}else if self>0.0{1.0}else{-1.0}}})*};}impl_signed_integer!{i8,i16,i32,i64,i128,isize}impl_signed_float!{f32,f64}}pub use signed::*;pub trait Recip{fn recip(self)->Self;}impl Recip for f32{fn recip(self)->Self{self.recip()}}impl Recip for f64{fn recip(self)->Self{self.recip()}}}
        pub mod eratosthenes {use crate::__cargo_equip::preludes::eratosthenes::*;use numeric_traits::Integer;pub struct Eratosthenes{n:usize,fs:Vec<u8>,}impl Eratosthenes{pub fn new(n:usize)->Self{if n==0{return Self{n:0,fs:vec![]};}let sz=n.ceil_div(30);let mut fs=vec![0xff_u8;sz];match n%30{29.. =>fs[sz-1]=0xff,23.. =>fs[sz-1]=0x7f,19.. =>fs[sz-1]=0x3f,17.. =>fs[sz-1]=0x1f,13.. =>fs[sz-1]=0x0f,11.. =>fs[sz-1]=0x07,7.. =>fs[sz-1]=0x03,1.. =>fs[sz-1]=0x01,_=>{}}fs[0]&=!1;'a:for i0 in 0..sz{let mut f=fs[i0];while f!=0{let i1=f.lsb_index();let x1=MOD_30[i1];if(i0*30+x1).pow(2)>n{break 'a;}let mut j0=i0*(30*i0+2*x1)+(x1*x1)/30;let mut j1=i1;while j0<sz{fs[j0]&=MUL_MASK[i1][j1];j0+=i0*D1[j1]+D2[i1][j1];j1=(j1+1)%8;}f&=f-1;}}Self{n,fs}}pub fn primes(&self)->impl Iterator<Item=usize>+'_{[2,3,5].into_iter().filter(|&p|p<=self.n).chain(self.fs.iter().enumerate().flat_map(|(i,&f)|{let mut f=f;std::iter::from_fn(move||{(f!=0).then(||{let j=f.lsb_index();f&=f-1;i*30+MOD_30[j]})})}))}pub fn is_prime(&self,x:usize)->bool{assert!(x<=self.n);match x{2|3|5=>true,_=>Self::id(x).map_or(false,|i|self.fs[i/30]>>(i%30)&1!=0),}}fn id(x:usize)->Option<usize>{if x<=6{return None;}let offset=x/30*8;let res=match x%30{1=>0,7=>1,11=>2,13=>3,17=>4,19=>5,23=>6,29=>7,_=>return None,}+offset;Some(res)}}const MOD_30:[usize;8]=[1,7,11,13,17,19,23,29];const D1:[usize;8]=[6,4,2,4,2,4,6,2];const D2:[[usize;8];8]=init_d2();const MUL_MASK:[[u8;8];8]=init_mul_mask();const fn init_mul_mask()->[[u8;8];8]{let mut mul=[[0;8];8];let mut i=0;while i<8{let mut j=0;while j<8{let x=MOD_30[i]*MOD_30[j]%30;let k=match x{1=>0,7=>1,11=>2,13=>3,17=>4,19=>5,23=>6,29=>7,_=>unreachable!(),};mul[i][j]=!(1<<k);j+=1;}i+=1;}mul}const fn init_d2()->[[usize;8];8]{let mut d2=[[0;8];8];let mut i=0;while i<8{let mut j=0;while j<8{let x=MOD_30[i]*(MOD_30[j]+D1[j])/30;let y=MOD_30[i]*MOD_30[j]/30;d2[i][j]=x-y;j+=1;}i+=1;}d2}}
    }

    pub(crate) mod macros {
        pub mod numeric_traits {}
        pub mod eratosthenes {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod numeric_traits {}
        pub mod eratosthenes {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::numeric_traits;}
    }
}
0