#1106490 (Rust) No.8030 ミラー・ラビン素数判定法のテスト

提出ソース
結果

問題	No.8030 ミラー・ラビン素数判定法のテスト
ユーザー	👑 Mizar
提出日時	2025-07-23 12:53:59
言語	Rust (1.83.0 + proconio)
結果	AC
実行時間	13 ms / 9,973 ms
コード長	30,186 bytes
コンパイル時間	24,343 ms
コンパイル使用メモリ	394,416 KB
実行使用メモリ	7,716 KB
最終ジャッジ日時	2025-07-23 12:54:30
合計ジャッジ時間	25,409 ms
ジャッジサーバーID （参考情報）	judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 10
権限があれば一括ダウンロードができます
ソースコード

raw source code
#![allow(unexpected_cfgs)]
pub use __cargo_equip::prelude::*;

use crate::__cargo_equip::crates::{bpsw::*, fastin::*};
use std::io::prelude::*;

pub fn solve<R: BufRead>(mut input: R) -> std::io::Result<()> {
    // Initialize.
    #[rustfmt::skip] #[cfg(tcheck)] let tins = std::time::Instant::now();
    #[rustfmt::skip] #[cfg(tcheck)] let mut durs = Vec::with_capacity(16);
    let mut bw = std::io::BufWriter::with_capacity(65536, std::io::stdout().lock());
    #[rustfmt::skip] #[cfg(tcheck)] durs.push((tins.elapsed(), "initial"));

    input! { source = &mut input, n: usize }
    for _ in 0..n {
        input! { source = &mut input, xt: Bytes }
        bw.write_all(&xt)?;
        let x = parse_u64(&xt);
        let isprime = primetest_u64_bpsw(x);
        bw.write_all(if isprime { b" 1\n" } else { b" 0\n" })?;
    }

    #[rustfmt::skip] #[cfg(tcheck)] durs.push((tins.elapsed(), "solve"));
    bw.flush()?;
    #[rustfmt::skip] #[cfg(tcheck)] durs.push((tins.elapsed(), "output"));

    // Execution Time.
    #[rustfmt::skip] #[cfg(tcheck)] for (dur, s) in durs.iter() { eprintln!("{:.6} {}", dur.as_secs_f64(), s); };
    Ok(())
}

#[cfg(not(target_os = "linux"))]
fn launch() -> std::io::Result<()> {
    solve(std::io::stdin().lock())
}
#[cfg(target_os = "linux")]
fn launch() -> std::io::Result<()> {
    use std::os::unix::io::FromRawFd;
    match unsafe { std::fs::File::from_raw_fd(0) }.metadata() {
        Ok(metadata) if metadata.is_file() => {
            let filelen = metadata.len();
            let input = unsafe { mmap(std::ptr::null_mut(), filelen as usize, 1, 2, 0, 0) };
            solve(unsafe { std::slice::from_raw_parts(input, filelen as usize) })
        }
        _ => solve(std::io::stdin().lock()),
    }
}

#[cfg(target_os = "linux")]
#[link(name = "c")]
#[rustfmt::skip]
extern "C" {
    pub fn mmap(addr: *mut u8, length: usize, prot: i32, flags: i32, fd: i32, off: isize) -> *mut u8;
}

pub fn main() -> std::io::Result<()> {
    const USE_THREAD: bool = false;
    if USE_THREAD {
        // In order to avoid potential stack overflow, spawn a new thread.
        let stack_size = 134_217_728; // 128 MB
        let thd = std::thread::Builder::new().stack_size(stack_size);
        thd.spawn(launch).unwrap().join().unwrap()
    } else {
        launch()
    }
}

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

///  # Bundled libraries
/// 
///  - `path+file:///home/mizar/compete-rust-workspace/mzr-library/crates/integer/issq#mizar-competitive-integer-issq@0.0.0`       published in https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` as `crate::__cargo_equip::crates::issq`
///  - `path+file:///home/mizar/compete-rust-workspace/mzr-library/crates/integer/jacobi#mizar-competitive-integer-jacobi@0.0.0`   published in https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` as `crate::__cargo_equip::crates::jacobi`
///  - `path+file:///home/mizar/compete-rust-workspace/mzr-library/crates/integer/montodd#mizar-competitive-integer-montodd@0.0.0` published in https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` as `crate::__cargo_equip::crates::montodd`
///  - `path+file:///home/mizar/compete-rust-workspace/mzr-library/crates/integer/sqrt#mizar-competitive-integer-sqrt@0.0.0`       published in https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` as `crate::__cargo_equip::crates::sqrt`
///  - `path+file:///home/mizar/compete-rust-workspace/mzr-library/crates/io/fastin#mizar-competitive-io-fastin@0.0.0`             published in https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` as `crate::__cargo_equip::crates::fastin`
///  - `path+file:///home/mizar/compete-rust-workspace/mzr-library/crates/misc/invariant#mizar-competitive-misc-invariant@0.0.0`   published in https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` as `crate::__cargo_equip::crates::invariant`
///  - `path+file:///home/mizar/compete-rust-workspace/mzr-library/crates/misc/primint#mizar-competitive-misc-primint@0.0.0`       published in https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` as `crate::__cargo_equip::crates::primint`
///  - `path+file:///home/mizar/compete-rust-workspace/mzr-library/crates/prime/bpsw#mizar-competitive-prime-bpsw@0.0.0`           published in https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` as `crate::__cargo_equip::crates::bpsw`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod issq {use crate::__cargo_equip::preludes::issq::*;use crate::__cargo_equip::crates::sqrt::*;macro_rules!fn_isqrt_n{($sqrt_newton:ident,$sqrt_exact:ident,$issq_newton:ident,$issq_mod32:ident,$issq_mod48:ident,$issq_mod4095:ident,$issq:ident,$x:ty,$w:literal)=>{pub fn$issq_mod32(x:$x)->bool{(0x02030213u32>>((x as u32)&31))&1==1}pub fn$issq_mod48(x:$x)->bool{(0x1202010213u64>>(x%48))&1==1}pub fn$issq_mod4095(x:$x)->bool{const SQTABLE_MOD4095:[u64;64]=[0x2001002010213,0x4200001008028001,0x20000010004,0x80200082010,0x1800008200044029,0x120080000010,0x2200000080410400,0x8100041000200800,0x800004000020100,0x402000400082201,0x9004000040,0x800002000880,0x18002000012000,0x801208,0x26100000804010,0x80000080000002,0x108040040101045,0x20c00004000102,0x400000100c0010,0x1300000040208,0x804000020010000,0x1008402002400080,0x201001000200040,0x4402000000806000,0x10402000000,0x1040008001200801,0x4080000000020400,0x10083080000002,0x8220140000040000,0x800084020100000,0x80010400010000,0x1200020108008060,0x180000000,0x400002400000018,0x4241000200,0x100800000000,0x10201008400483,0xc008000208201000,0x800420000100,0x2010002000410,0x28041000000,0x4010080000024,0x400480010010080,0x200040028000008,0x100810084020,0x20c0401000080000,0x1000240000220000,0x4000020800,0x410000000480000,0x8004008000804201,0x806020000104000,0x2080002000211000,0x1001008001000,0x20000010024000,0x480200002040000,0x48200044008000,0x100000000010080,0x80090400042,0x41040200800200,0x4000020100110,0x2000400082200010,0x1008200000000040,0x2004800002,0x2002010000080,];let p=(x%4095)as usize;(SQTABLE_MOD4095[p>>6]>>(p&63))&1==1}pub fn$issq_newton(x:$x)->bool{let sqrt_f=$sqrt_newton(x);sqrt_f*sqrt_f==x}pub fn$issq(x:$x)->bool{$issq_mod32(x)&&$issq_mod4095(x)&&$issq_newton(x)}pub fn$sqrt_exact(x:$x)->Option<$x>{if$issq_mod32(x)&&$issq_mod4095(x){let sqrt_f=$sqrt_newton(x);if sqrt_f*sqrt_f==x{return Some(sqrt_f);}}None}};}fn_isqrt_n!(sqrt_floor,isqrt_64_exact,issq_u64_newton,issq_u64_mod32,issq_u64_mod48,issq_u64_mod4095,issq_u64,u64,32);fn_isqrt_n!(sqrt_floor,isqrt_32_exact,issq_u32_newton,issq_u32_mod32,issq_u32_mod48,issq_u32_mod4095,issq_u32,u32,16);}
        pub mod jacobi {use crate::__cargo_equip::preludes::jacobi::*;use crate::__cargo_equip::crates::{invariant::*,primint::*};pub fn kronecker_i64(ai:i64,ni:i64)->i32{if ni==0{match ai{1|-1=>1,_=>0,}}else if ni<0{if ai<0{-kronecker_i64u64(ai,ni.wrapping_neg()as u64)}else{kronecker_i64u64(ai,ni.wrapping_neg()as u64)}}else{kronecker_i64u64(ai,ni as u64)}}pub fn kronecker_i64u64(ai:i64,n:u64)->i32{if n==0{match ai{1|-1=>1,_=>0,}}else if(n&1)==0{let trz=n.trailing_zeros();match ai&7{0|2|4|6=>0,1|7=>jacobi_i64(ai,n),3|5=>{if trz&1==0{jacobi_i64(ai,n>>trz)}else{-jacobi_i64(ai,n>>trz)}}_=>unreachable!(),}}else{jacobi_i64(ai,n)}}pub fn kronecker_u64(a:u64,n:u64)->i32{if n==0{match a{1=>1,_=>0,}}else if(n&1)==0{let trz=n.trailing_zeros();match a&7{0|2|4|6=>0,1|7=>jacobi_inner(a,n>>trz,1),3|5=>jacobi_inner(a,n>>trz,if trz&1==0{1}else{-1}),_=>unreachable!(),}}else{jacobi_inner(a,n,1)}}pub fn jacobi_i64(ai:i64,n:u64)->i32{debug_assert_eq!(n&1,1);if ai<0{jacobi_inner(ai.wrapping_neg()as u64,n,if(n&3)==3{-1}else{1},)}else{jacobi_inner(ai as u64,n,1)}}pub fn jacobi_i32(ai:i32,n:u32)->i32{debug_assert_eq!(n&1,1);if ai<0{jacobi_inner(ai.wrapping_neg()as u32,n,if(n&3)==3{-1}else{1},)}else{jacobi_inner(ai as u32,n,1)}}pub fn jacobi<U:UPrimInt>(a:U,n:U)->i32{debug_assert_eq!(n.as_u32()%2,1);jacobi_inner(a,n,1)}fn jacobi_inner<U:UPrimInt>(mut a:U,mut n:U,mut j:i32)->i32{while!a.is_zero()&&n>U::from(255){let ba=a.trailing_zeros();if(ba&1)!=0&&((n+U::from(2))&U::from(5))==U::from(5){j=-j;}a>>=ba;if(a&n&U::from(3))==U::from(3){j=-j;}invariant!(!a.is_zero());let t=n%a;n=a;a=t;if a>(n>>1){a=n-a;if(n&U::from(3))==U::from(3){j=-j;}}}while!a.is_zero(){let ba=a.trailing_zeros();if(ba&1)!=0&&((n+U::from(2))&U::from(5))==U::from(5){j=-j;}a>>=ba;if a<n{if a>(n>>1){a=n-a;if(n&U::from(3))==U::from(3){j=-j;}let ba=a.trailing_zeros();if(ba&1)!=0&&((n+U::from(2))&U::from(5))==U::from(5){j=-j;}a>>=ba;}if(a&n&U::from(3))==U::from(3){j=-j;}let t=n-a;n=a;a=t;}else{a-=n;}}if n==U::from(1){j}else{0}}}
        pub mod montodd {use crate::__cargo_equip::preludes::montodd::*;use crate::__cargo_equip::crates::invariant::*;pub trait MontVal<T,BitCountType=u32>{fn m(&self)->T;fn mi(&self)->T;fn mh(&self)->T;fn r(&self)->T;fn rn(&self)->T;fn r2(&self)->T;fn d(&self)->T;fn k(&self)->BitCountType;}pub trait MontOps<T,BitCountType=u32>{fn add(&self,a:T,b:T)->T;fn sub(&self,a:T,b:T)->T;fn div2(&self,ar:T)->T;fn mrmul(&self,ar:T,br:T)->T;fn mrmadd(&self,ar:T,br:T,cr2:T)->T;fn mrmaddadd(&self,ar:T,br:T,cr2:T,dr2:T)->T;fn mr(&self,ar:T)->T;fn ar(&self,a:T)->T;fn pow(&self,ar:T,b:T)->T;}pub trait MontModN<T,BitCountType=u32>{fn modn(&self,x:T)->T;}pub trait MontNew<T,U=T,BitCountType=u32>{fn new_modulus(n:T)->Self;}pub struct Mont<T,BitCountType=u32>{m:T,mi:T,mh:T,r:T,rn:T,r2:T,d:T,k:BitCountType,}macro_rules!impl_mont_val_pr{($x:ty)=>{impl MontVal<$x>for Mont<$x>{fn m(&self)->$x{self.m}fn mi(&self)->$x{self.mi}fn mh(&self)->$x{self.mh}fn r(&self)->$x{self.r}fn rn(&self)->$x{self.rn}fn r2(&self)->$x{self.r2}fn d(&self)->$x{self.d}fn k(&self)->u32{self.k}}};}impl_mont_val_pr!(u64);impl_mont_val_pr!(u32);fn mont_r2_u64(m:u64)->(u64,u64){let(mut r1,mut r2):(u64,u64);unsafe{core::arch::asm!("div {0}","mov {1},rdx","xor rax,rax","div {0}",in(reg)m,out(reg)r1,inout("rax")0u64=>_,inout("rdx")1u64=>r2,options(pure,nomem,nostack))}(r1,r2)}fn mont_r2_u32(m:u32)->(u32,u32){let(mut r1,mut r2):(u32,u32);unsafe{core::arch::asm!("div {0:e}","mov {1:e},edx","xor eax,eax","div {0:e}",in(reg)m,out(reg)r1,inout("eax")0u32=>_,inout("edx")1u32=>r2,options(pure,nomem,nostack))}(r1,r2)}fn mont_sub_u64(a:u64,b:u64,m:u64)->u64{let mut r:u64;unsafe{core::arch::asm!("sub {0:r},{1:r}","cmovb {3:r},{2:r}","add {3:r},{0:r}",inout(reg)a=>_,in(reg)b,in(reg)m,inout(reg)0u64=>r,options(pure,nomem,nostack))}r}fn mont_sub_u32(a:u32,b:u32,m:u32)->u32{let mut r:u32;unsafe{core::arch::asm!("sub {0:e},{1:e}","cmovb {3:e},{2:e}","add {3:e},{0:e}",inout(reg)a=>_,in(reg)b,in(reg)m,inout(reg)0u32=>r,options(pure,nomem,nostack))}r}macro_rules!impl_mont_ops{($x:ty,$y:ty,$y2:ty,$w:literal,$msub:ident)=>{impl MontOps<$y>for$x{fn add(&self,a:$y,b:$y)->$y{debug_assert!(a<self.m());debug_assert!(b<self.m());$msub(a,self.m()-b,self.m())}fn sub(&self,a:$y,b:$y)->$y{debug_assert!(a<self.m());debug_assert!(b<self.m());$msub(a,b,self.m())}fn div2(&self,ar:$y)->$y{debug_assert!(ar<self.m());let t=ar>>1;t.wrapping_add((((ar&1)!=0)as$y).wrapping_neg()&self.mh())}fn mrmul(&self,ar:$y,br:$y)->$y{debug_assert!(ar<self.m());debug_assert!(br<self.m());let(m,mi)=(self.m(),self.mi());let t:$y2=(ar as$y2)*(br as$y2);$msub((t>>$w)as$y,(((((t as$y).wrapping_mul(mi))as$y2)*(m as$y2))>>$w)as$y,m,)}fn mrmadd(&self,ar:$y,br:$y,cr2:$y)->$y{debug_assert!(ar<self.m());debug_assert!(br<self.m());debug_assert!(cr2<self.m());let(m,mi)=(self.m(),self.mi());let t:$y2=(ar as$y2)*(br as$y2)+(cr2 as$y2);$msub((t>>$w)as$y,(((((t as$y).wrapping_mul(mi))as$y2)*(m as$y2))>>$w)as$y,m,)}fn mrmaddadd(&self,ar:$y,br:$y,cr2:$y,dr2:$y)->$y{debug_assert!(ar<self.m());debug_assert!(br<self.m());debug_assert!(cr2<self.m());debug_assert!(dr2<self.m());let(m,mi)=(self.m(),self.mi());let t:$y2=(ar as$y2)*(br as$y2)+(cr2 as$y2)+(dr2 as$y2);$msub((t>>$w)as$y,(((((t as$y).wrapping_mul(mi))as$y2)*(m as$y2))>>$w)as$y,m,)}fn mr(&self,ar:$y)->$y{debug_assert!(ar<self.m());let(m,mi)=(self.m(),self.mi());$msub(0,((((ar.wrapping_mul(mi))as$y2)*(m as$y2))>>$w)as$y,m,)}fn ar(&self,a:$y)->$y{debug_assert!(a<self.m());self.mrmul(a,self.r2())}fn pow(&self,mut ar:$y,mut b:$y)->$y{debug_assert!(ar<self.m());if b==0{return self.r();}while b&1==0{ar=self.mrmul(ar,ar);b>>=1;}let mut t=ar;b>>=1;while b!=0{ar=self.mrmul(ar,ar);if(b&1)!=0{t=self.mrmul(t,ar);}b>>=1;}t}}};}impl_mont_ops!(Mont<u64>,u64,u128,64,mont_sub_u64);impl_mont_ops!(Mont<u32>,u32,u64,32,mont_sub_u32);macro_rules!impl_mont_modn{($x:ty)=>{impl MontModN<$x>for Mont<$x>{fn modn(&self,x:$x)->$x{if x<self.m(){x}else{x%self.m()}}}};}impl_mont_modn!(u64);impl_mont_modn!(u32);macro_rules!impl_mont_new{($x:ty,$x2:ty,$mont_r2:ident)=>{impl MontNew<$x>for Mont<$x>{fn new_modulus(m:$x)->Self{debug_assert!(m>1&&(m&1)==1);let mi={let bits=(!(0 as$x)).count_ones();let mut x=m.wrapping_mul(3)^2;let mut y=(1 as$x).wrapping_sub(m.wrapping_mul(x));let mut w=5;while w<bits{x=x.wrapping_mul(y.wrapping_add(1));y=y.wrapping_mul(y);w*=2;}x};debug_assert_eq!(m.wrapping_mul(mi),1);let mh=(m>>1)+1;invariant!(m!=0);let(r,r2)=$mont_r2(m);let rn=m-r;let mut d=m-1;let k=d.trailing_zeros();d>>=k;debug_assert_eq!(Self{m,mi,mh,r,rn,r2,d,k}.mr(r),1);debug_assert_eq!(Self{m,mi,mh,r,rn,r2,d,k}.mrmul(1,r2),r);Self{m,mi,mh,r,rn,r2,d,k,}}}};}impl_mont_new!(u64,u128,mont_r2_u64);impl_mont_new!(u32,u64,mont_r2_u32);}
        pub mod sqrt {use crate::__cargo_equip::preludes::sqrt::*;use crate::__cargo_equip::crates::{invariant::*,primint::*};pub fn sqrt_floor<U:UPrimInt>(x:U)->U{if x<=U::one(){return x;}if U::BITS>32&&x<=U::from_u32(!0u32){U::from_u32(sqrt_floor(x.as_u32()))}else if U::BITS<=32||x>U::from_u64(!0u64){let y=(x-U::one()).leading_zeros();let log2=U::BITS-1-y;let k=(U::BITS>>1)-(y>>1);let mut s=U::one()<<k;let mut t=(s+(x>>k))>>1;for _ in 0..match log2{0..=3=>0,4..=9=>1,10..=22=>2,23..=47=>3,48..=98=>4,99..=199=>5,_=>32,}{if t>=s{return s;}s=t;invariant!(!s.is_zero());t=(s+x/s)>>1;}match t.checked_mul(t){Some(u)if u<=x=>t,_=>t-U::one(),}}else{use std::cmp::Ordering::*;let x=x.as_u64();match x{0..=0xfffffffc00000003=>{let mut s=(x as f64).sqrt()as u64;U::from_u64(match((s+1)*(s+1)).cmp(&x){Less=>loop{s+=1;match((s+1)*(s+1)).cmp(&x){Less=>{}Equal=>break s+1,Greater=>break s,}},Equal=>s+1,Greater=>{while s*s>x{s-=1;}s}})}0xfffffffc00000004..=0xfffffffe00000000=>U::from_u32((!0u32)-1),0xfffffffe00000001..=0xffffffffffffffff=>U::from_u32(!0u32),}}}pub fn sqrt_ceil<U:UPrimInt>(x:U)->U{let s=sqrt_floor(x);if x>s*s{s+U::one()}else{s}}}
        pub mod fastin {use crate::__cargo_equip::preludes::fastin::*;pub use crate::__cargo_equip::macros::fastin::*;#[macro_export(local_inner_macros)]macro_rules!__cargo_equip_macro_def_fastin_read_value{($b:expr,($($t:tt),*))=>{($(read_value!($b,$t)),*)};($b:expr,[$t:tt;$len:expr])=>{(0..$len).map(|_|read_value!($b,$t)).collect::<Vec<_>>()};($b:expr,byte)=>{token($b,|s|s[0],|_|None)};($b:expr,Bytes)=>{token($b,|s|s.to_vec(),|_|None)};($b:expr,Chars)=>{token($b,|s|std::str::from_utf8(s).unwrap().chars().collect::<Vec<_>>(),|_|None)};($b:expr,u8_1)=>{read_value!($b,u8)-1};($b:expr,u16_1)=>{read_value!($b,u16)-1};($b:expr,u32_1)=>{read_value!($b,u32)-1};($b:expr,u64_1)=>{read_value!($b,u64)-1};($b:expr,usize1)=>{read_value!($b,usize)-1};($b:expr,Usize1)=>{read_value!($b,usize)-1};($b:expr,Isize1)=>{read_value!($b,isize)-1};($b:expr,u8)=>{read_value!($b,u64)as u8};($b:expr,u16)=>{read_value!($b,u64)as u16};($b:expr,u32)=>{read_value!($b,u64)as u32};($b:expr,u64)=>{token($b,parse_u64,cparse_u64)};($b:expr,u128)=>{token($b,parse_u128,cparse_u128)};($b:expr,usize)=>{read_value!($b,u64)as usize};($b:expr,i8)=>{read_value!($b,i64)as i8};($b:expr,i16)=>{read_value!($b,i64)as i16};($b:expr,i32)=>{read_value!($b,i64)as i32};($b:expr,i64)=>{token($b,parse_i64,cparse_i64)};($b:expr,i128)=>{token($b,parse_i128,cparse_i128)};($b:expr,isize)=>{read_value!($b,i64)as isize};($b:expr,$t:ty)=>{token($b,|s|std::str::from_utf8(s).unwrap().parse::<$t>().unwrap(),|_|None)};}macro_rules!read_value{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_fastin_read_value!{$($tt)*})}#[macro_export(local_inner_macros)]macro_rules!__cargo_equip_macro_def_fastin_input_inner{($b:expr)=>{};($b:expr,)=>{};($b:expr,mut$var:ident:$t:tt$($r:tt)*)=>{let mut$var=read_value!($b,$t);input_inner!{$b$($r)*}};($b:expr,$var:ident:$t:tt$($r:tt)*)=>{let$var=read_value!($b,$t);input_inner!{$b$($r)*}};}macro_rules!input_inner{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_fastin_input_inner!{$($tt)*})}#[macro_export(local_inner_macros)]macro_rules!__cargo_equip_macro_def_fastin_input{(source=$s:expr,$($r:tt)*)=>{input_inner!{$s,$($r)*}};($($r:tt)*)=>{let mut i=std::io::stdin().lock();input_inner!{&mut i,$($r)*}std::mem::drop(i);};}macro_rules!input{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_fastin_input!{$($tt)*})}macro_rules!invariant{($expr:expr)=>{debug_assert!($expr);if!($expr){#[allow(unused_unsafe)]unsafe{core::hint::unreachable_unchecked()};}};}pub fn token<R:std::io::BufRead,T>(r:&mut R,f:impl Fn(&[u8])->T,g:impl Fn(&[u8])->Option<(T,usize)>,)->T{let(b,l)=loop{let b=r.fill_buf().unwrap();if b.is_empty(){panic!("Unexpected end of input");}if let Some(p)=b.iter().position(|&c|b' '<c){break(&b[p..],p);}let l=b.len();r.consume(l);};if let Some((x,p))=g(b){r.consume(l+p);return x;}if let Some(p)=b.iter().position(|&c|c<=b' '){let t=&b[..p];invariant!(!t.is_empty());let x=f(t);r.consume(l+p+1);return x;}let mut t=b.to_vec();r.consume(l+t.len());while let Ok(b)=r.fill_buf(){if b.is_empty(){break;}if let Some(p)=b.iter().position(|&c|c<=b' '){t.extend_from_slice(&b[..p]);r.consume(p+1);break;}let l=b.len();t.extend_from_slice(b);r.consume(l);}invariant!(!t.is_empty());f(&t)}const E:[u64;20]={let(mut e,mut p)=([1;20],0);while p<19{e[p+1]=e[p]*10;p+=1;}e};const E8:u64=100000000;const EH:u64=E8*E8;const EW:u128=EH as _;const MH:u128=0xf0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0;const DH:u128=MH&(MH>>2);const M8:u64=MH as _;const D8:u64=DH as _;fn u32b(b:[u8;4])->u32{u32::from_le_bytes(b)}fn u32s(b:&[u8])->u32{u32b(b[..4].try_into().unwrap())}fn u64b(b:[u8;8])->u64{u64::from_le_bytes(b)}fn u64s(b:&[u8])->u64{u64b(b[..8].try_into().unwrap())}fn u32c(b:u32)->[u8;4]{u32::to_le_bytes(b)}fn u64c(b:u64)->[u8;8]{u64::to_le_bytes(b)}fn q2(b:u16)->u64{b.wrapping_mul(2561)as u64>>8}fn q4(b:u32)->u64{((b.wrapping_mul(2561)>>8)&0xff00ff).wrapping_mul(6553601)as u64>>16}fn q8(b:u64)->u64{((((b.wrapping_mul(2561)>>8)&0xff00ff00ff00ff).wrapping_mul(6553601)>>16)&0xffff0000ffff).wrapping_mul((10000<<32)+1)>>32}fn q16(b:u128)->u64{q8(b as u64)*E8+q8((b>>64)as u64)}fn p2(b:[u8;2])->u64{q2(u16::from_le_bytes(b)&3855)}fn p4(b:[u8;4])->u64{q4(u32::from_le_bytes(b)&0xf0f0f0f)}fn p8(b:[u8;8])->u64{q8(u64::from_le_bytes(b)&(M8>>4))}fn p16(b:[u8;16])->u64{q16(u128::from_le_bytes(b)&(MH>>4))}fn p2s(s:&[u8])->u64{p2(s[..2].try_into().unwrap())}fn p4s(s:&[u8])->u64{p4(s[..4].try_into().unwrap())}fn p8s(s:&[u8])->u64{p8(s[..8].try_into().unwrap())}fn p16s(s:&[u8])->u64{p16(s[..16].try_into().unwrap())}fn p(s:&[u8])->u64{match s.len(){0=>0,1=>(s[0]&15)as u64,2=>p2s(s),3=>((s[0]&15)as u64)*100+p2s(&s[1..]),4=>p4s(s),5..=8=>p8(u64c((u32s(s)<<(8*(8-s.len())))as u64|((u32s(&s[(s.len()-4)..])as u64)<<32),)),9..=16=>p8(u64c(u64s(s)<<(8*(16-s.len()))))*E8+p8s(&s[(s.len()-8)..]),_=>unreachable!(),}}pub fn parse_u64(s:&[u8])->u64{match s.len(){0..=16=>p(s),17..=20=>{p4(u32c(u32s(s)<<(8*(20-s.len()))))as u64*EH+p16s(&s[(s.len()-16)..])}_=>{let c=s.rchunks_exact(8);let l=p(c.remainder());c.rfold(l,|a,b|a*E8+p8s(b))}}}pub fn parse_u128(s:&[u8])->u128{match s.len(){0..=19=>parse_u64(s)as u128,20..=35=>{let(t,u)=s.split_at(s.len()-16);parse_u64(t)as u128*EW+p16s(u)as u128}36..=39=>{p8(u64c(u64s(&s[..8])<<(8*(40-s.len()))))as u128*(EW*EW)+p16s(&s[s.len()-32..])as u128*EW+p16s(&s[s.len()-16..])as u128}_=>{let c=s.rchunks_exact(16);let l=p(c.remainder())as u128;c.rfold(l,|a,b|a*EW+(p16s(b)as u128))}}}pub fn parse_i64(s:&[u8])->i64{if s[0]==b'-'{-(parse_u64(&s[1..])as i64)}else{parse_u64(s)as i64}}pub fn parse_i128(s:&[u8])->i128{if s[0]==b'-'{-(parse_u128(&s[1..])as i128)}else{parse_u128(s)as i128}}pub fn cparse_u64(mut s:&[u8])->Option<(u64,usize)>{if s.len()<24{return None;}let mut v={let b=u64s(s)^D8;let e=b&M8;if e>0{let e=e.trailing_zeros()as usize/8;return Some(if e>0{(q8(b<<(64-8*e)),e+1)}else{(0,1)});}q8(b)};{let b=u64s(&s[8..])^D8;let e=b&M8;if e>0{let e=e.trailing_zeros()as usize/8;return Some(if e>0{(v*E[e]+q8(b<<(64-8*e)),e+9)}else{(v,9)});}v=v*E8+q8(b);}{let b=u64s(&s[16..])^D8;let e=b&M8;if e>0{let e=e.trailing_zeros()as usize/8;return Some(if e>0{(v*E[e]+q8(b<<(64-8*e)),e+17)}else{(v,17)});}v=v*E8+q8(b);}let mut c=25;s=&s[24..];while s.len()>=8{let b=u64s(s)^D8;let e=b&M8;if e>0{let e=e.trailing_zeros()as usize/8;if e>0{v=v*E[e]+q8(b<<(64-8*e));c+=e;}return Some((v,c));}v=v*E8+q8(b);s=&s[8..];c+=8;}None}pub fn cparse_u128(mut s:&[u8])->Option<(u128,usize)>{if s.len()<40{return None;}let v={let b=u64s(s)^D8;let e=b&M8;if e>0{let e=e.trailing_zeros()as usize/8;return Some(if e>0{(q8(b<<(64-8*e))as u128,e+1)}else{(0,1)});}q8(b)};let v={let b=u64s(&s[8..])^D8;let e=b&M8;if e>0{let e=e.trailing_zeros()as usize/8;return Some(if e>0{((v*E[e]+q8(b<<(64-8*e)))as u128,e+9)}else{(v as u128,9)});}v*E8+q8(b)};let v2={let b=u64s(&s[16..])^D8;let e=b&M8;if e>0{let e=e.trailing_zeros()as usize/8;return Some(if e>0{(v as u128*E[e]as u128+q8(b<<(64-8*e))as u128,e+17,)}else{(v as u128,17)});}q8(b)};let v3={let b=u64s(&s[24..])^D8;let e=b&M8;if e>0{let e=e.trailing_zeros()as usize/8;return Some(if e>0{(v as u128*E[e+8]as u128+(v2*E[e]+q8(b<<(64-8*e)))as u128,e+25,)}else{(v as u128*E8 as u128+v2 as u128,25)});}q8(b)};let mut v=v as u128*EW+(v2*E8+v3)as u128;{let b=u64s(&s[32..])^D8;let e=b&M8;if e>0{let e=e.trailing_zeros()as usize/8;if e>0{v=v*E[e]as u128+q8(b<<(64-8*e))as u128;}return Some((v,e+33));}v=v*E8 as u128+q8(b)as u128;}let mut c=40;s=&s[40..];while s.len()>=8{let b=u64s(s)^D8;let e=b&M8;if e>0{let e=e.trailing_zeros()as usize/8;if e>0{v=v*E[e]as u128+q8(b<<(64-8*e))as u128;c+=e;}return Some((v,c));}v=v*E8 as u128+q8(b)as u128;s=&s[8..];c+=8;}None}pub fn cparse_i64(s:&[u8])->Option<(i64,usize)>{if s[0]==b'-'{cparse_u64(&s[1..]).map(|(v,c)|(-(v as i64),c+1))}else{cparse_u64(s).map(|(v,c)|(v as i64,c))}}pub fn cparse_i128(s:&[u8])->Option<(i128,usize)>{if s[0]==b'-'{cparse_u128(&s[1..]).map(|(v,c)|(-(v as i128),c+1))}else{cparse_u128(s).map(|(v,c)|(v as i128,c))}}}
        pub mod invariant {pub use crate::__cargo_equip::macros::invariant::*;#[macro_export]macro_rules!__cargo_equip_macro_def_invariant_invariant{($expr:expr)=>{debug_assert!($expr);if!($expr){#[allow(unused_unsafe)]unsafe{core::hint::unreachable_unchecked()};}};}macro_rules!invariant{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_invariant_invariant!{$($tt)*})}}
        pub mod primint {use std::ops;pub trait UPrimInt:Copy+Default+std::cmp::Ord+ops::Add<Output=Self>+ops::Sub<Output=Self>+ops::Mul<Output=Self>+ops::Div<Output=Self>+ops::Rem<Output=Self>+ops::AddAssign+ops::SubAssign+ops::MulAssign+ops::DivAssign+ops::RemAssign+ops::Shl<u32,Output=Self>+ops::Shr<u32,Output=Self>+ops::ShlAssign<u32>+ops::ShrAssign<u32>+ops::BitAnd<Output=Self>+ops::BitOr<Output=Self>+ops::BitXor<Output=Self>+ops::BitAndAssign+ops::BitOrAssign+ops::BitXorAssign+ops::Not<Output=Self>+std::convert::From<u8>{const BITS:u32;fn count_zeros(self)->u32;fn count_ones(self)->u32;fn trailing_zeros(self)->u32;fn leading_zeros(self)->u32;fn checked_add(self,rhs:Self)->Option<Self>;fn checked_sub(self,rhs:Self)->Option<Self>;fn checked_mul(self,rhs:Self)->Option<Self>;fn checked_pow(self,exp:u32)->Option<Self>;fn wrapping_add(self,rhs:Self)->Self;fn wrapping_sub(self,rhs:Self)->Self;fn wrapping_neg(self)->Self;fn wrapping_mul(self,rhs:Self)->Self;fn overflowing_add(self,rhs:Self)->(Self,bool);fn overflowing_sub(self,rhs:Self)->(Self,bool);fn overflowing_neg(self)->(Self,bool);fn overflowing_mul(self,rhs:Self)->(Self,bool);fn pow(self,exp:u32)->Self;fn zero()->Self;fn one()->Self;fn is_zero(self)->bool;fn as_u8(self)->u8;fn as_u16(self)->u16;fn as_u32(self)->u32;fn as_u64(self)->u64;fn as_u128(self)->u128;fn as_usize(self)->usize;fn from_u32(x:u32)->Self;fn from_u64(x:u64)->Self;fn from_u128(x:u128)->Self;fn from_usize(x:usize)->Self;}macro_rules!impl_uprimint{($t:ty)=>{impl UPrimInt for$t{const BITS:u32=(0 as$t).count_zeros();fn count_zeros(self)->u32{self.count_zeros()}fn count_ones(self)->u32{self.count_ones()}fn trailing_zeros(self)->u32{self.trailing_zeros()}fn leading_zeros(self)->u32{self.leading_zeros()}fn checked_add(self,rhs:$t)->Option<$t>{self.checked_add(rhs)}fn checked_sub(self,rhs:$t)->Option<$t>{self.checked_sub(rhs)}fn checked_mul(self,rhs:$t)->Option<$t>{self.checked_mul(rhs)}fn checked_pow(self,exp:u32)->Option<$t>{self.checked_pow(exp)}fn wrapping_add(self,rhs:$t)->$t{self.wrapping_add(rhs)}fn wrapping_sub(self,rhs:$t)->$t{self.wrapping_sub(rhs)}fn wrapping_neg(self)->$t{self.wrapping_neg()}fn wrapping_mul(self,rhs:$t)->$t{self.wrapping_mul(rhs)}fn overflowing_add(self,rhs:$t)->($t,bool){self.overflowing_add(rhs)}fn overflowing_sub(self,rhs:$t)->($t,bool){self.overflowing_sub(rhs)}fn overflowing_neg(self)->($t,bool){self.overflowing_neg()}fn overflowing_mul(self,rhs:$t)->($t,bool){self.overflowing_mul(rhs)}fn pow(self,exp:u32)->Self{self.pow(exp)}fn zero()->$t{0 as$t}fn one()->$t{1 as$t}fn is_zero(self)->bool{self==(0 as$t)}fn as_u8(self)->u8{self as u8}fn as_u16(self)->u16{self as u16}fn as_u32(self)->u32{self as u32}fn as_u64(self)->u64{self as u64}fn as_u128(self)->u128{self as u128}fn as_usize(self)->usize{self as usize}fn from_u32(x:u32)->Self{x as Self}fn from_u64(x:u64)->Self{x as Self}fn from_u128(x:u128)->Self{x as Self}fn from_usize(x:usize)->Self{x as Self}}};}impl_uprimint!(u8);impl_uprimint!(u16);impl_uprimint!(u32);impl_uprimint!(u64);impl_uprimint!(u128);impl_uprimint!(usize);pub trait IPrimInt:Copy+Default+std::cmp::Ord+ops::Add<Output=Self>+ops::Sub<Output=Self>+ops::Neg<Output=Self>+ops::Mul<Output=Self>+ops::Div<Output=Self>+ops::Rem<Output=Self>+std::convert::From<i8>{const BITS:u32;fn zero()->Self;fn one()->Self;fn is_zero(self)->bool;}macro_rules!impl_iprimint{($t:ty)=>{impl IPrimInt for$t{const BITS:u32=(0 as$t).count_zeros();fn zero()->$t{0 as$t}fn one()->$t{1 as$t}fn is_zero(self)->bool{self==(0 as$t)}}};}impl_iprimint!(i8);impl_iprimint!(i16);impl_iprimint!(i32);impl_iprimint!(i64);impl_iprimint!(i128);impl_iprimint!(isize);}
        pub mod bpsw {use crate::__cargo_equip::preludes::bpsw::*;use crate::__cargo_equip::crates::{issq::*,jacobi::*};pub use crate::__cargo_equip::crates::{montodd::*,primint::*};pub trait PrimeTest<U>{fn primetest_base2(&self)->bool;fn primetest_miller(&self,base:U)->bool;fn primetest_lucas(&self)->bool;fn primetest_bpsw(&self)->bool;}pub fn lucas_dprobe<U:UPrimInt>(n:U)->Option<i32>{for d in(5u32..).step_by(2){match if(n&U::from(3))==U::from(3)&&(d&3)==3{-jacobi(U::from_u32(d),n)}else{jacobi(U::from_u32(d),n)}{-1=>{return Some(if(d&2)==0{d as i32}else{-(d as i32)});}0=>{if U::from_u32(d)<n{return None;}}_=>{}}if d==61&&issq_u64(n.as_u64()){return None;}}None}macro_rules!trait_primetest{($jacobi:ident,$issq:ident,$u:ty,$i:ty,$w:literal)=>{impl PrimeTest<$u>for Mont<$u>{fn primetest_base2(&self)->bool{let(r,rn,d,k)=(self.r(),self.rn(),self.d(),self.k());let mut br=self.pow(self.add(r,r),d);if br==r||br==rn{return true;}for _ in 1..k{br=self.mrmul(br,br);if br==rn{return true;}}false}fn primetest_miller(&self,mut base:$u)->bool{let(m,r,rn,d,k)=(self.m(),self.r(),self.rn(),self.d(),self.k());if base>=m{base=self.modn(base);if base==0{return true;}}let mut tr=self.pow(self.ar(base),d);if tr==r||tr==rn{return true;}for _ in 1..k{tr=self.mrmul(tr,tr);if tr==rn{return true;}}false}fn primetest_lucas(&self)->bool{let n=self.m();let d=match lucas_dprobe(n){Some(d)=>d,None=>return false,};let qm=self.ar(self.modn(if d<0{((1-d)as$u)/4}else{n-((d-1)as$u)/4}));let mut k=(n+1)<<(n+1).leading_zeros();let mut um=self.r();let mut vm=self.r();let mut qn=qm;let dm=self.ar(if d<0{n-self.modn((-d)as$u)}else{self.modn(d as$u)});k<<=1;while k!=0{um=self.mrmul(um,vm);vm=self.sub(self.mrmul(vm,vm),self.add(qn,qn));qn=self.mrmul(qn,qn);if(k>>($w-1))!=0{let uu=self.div2(self.add(um,vm));vm=self.div2(self.add(self.mrmul(dm,um),vm));um=uu;qn=self.mrmul(qn,qm);}k<<=1;}if um==0||vm==0{return true;}let mut x=(n+1)&(!n);x>>=1;while x!=0{um=self.mrmul(um,vm);vm=self.sub(self.mrmul(vm,vm),self.add(qn,qn));if vm==0{return true;}qn=self.mrmul(qn,qn);x>>=1;}false}fn primetest_bpsw(&self)->bool{self.primetest_base2()&&self.primetest_lucas()}}};}trait_primetest!(jacobi_i64,issq_u64,u64,i64,64);trait_primetest!(jacobi_i32,issq_u32,u32,i32,32);pub fn primetest_u64_bpsw(n:u64)->bool{if n==2{return true;}if n==1||(n&1)==0{return false;}let mont=Mont::<u64>::new_modulus(n);mont.primetest_bpsw()}}
    }

    pub(crate) mod macros {
        pub mod issq {}
        pub mod jacobi {}
        pub mod montodd {}
        pub mod sqrt {}
        pub mod fastin {pub use crate::{__cargo_equip_macro_def_fastin_input as input,__cargo_equip_macro_def_fastin_input_inner as input_inner,__cargo_equip_macro_def_fastin_read_value as read_value};}
        pub mod invariant {pub use crate::__cargo_equip_macro_def_invariant_invariant as invariant;}
        pub mod primint {}
        pub mod bpsw {}
    }

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

    mod preludes {
        pub mod issq {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{invariant,primint,sqrt};}
        pub mod jacobi {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{invariant,primint};}
        pub mod montodd {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::invariant;}
        pub mod sqrt {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{invariant,primint};}
        pub mod fastin {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::fastin::*;}
        pub mod invariant {}
        pub mod primint {}
        pub mod bpsw {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{invariant,issq,jacobi,montodd,primint};}
    }
}
yukicoder

結果

ソースコード
