結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー nPk
提出日時 2026-04-09 18:16:02
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 21 ms / 9,973 ms
コード長 15,457 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,176 ms
コンパイル使用メモリ 213,692 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-04-09 18:16:09
合計ジャッジ時間 5,452 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

pub use npk_cp_lib::prelude::*;

use std::io::stdin;

use input::{bind, FastInput};
use lib_modulo::prime::primality_test;
use proconio::fastout;

#[fastout]
fn main() {
    let mut input: FastInput<std::io::StdinLock<'_>> = FastInput::new(stdin().lock());
    bind! { input >> n: usize, x: [u64; n], }

    for x in x {
        if primality_test(x) {
            println!("{x} 1")
        } else {
            println!("{x} 0")
        }
    }
}

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

///  # Bundled libraries
/// 
///  - `git+https://github.com/qdot3/montgomery#lib-modulo@0.1.0`                                             licensed under `Apache-2.0 OR MIT` as `crate::npk_cp_lib::crates::lib_modulo`
/// 
///  # License and Copyright Notices
/// 
///  - `git+https://github.com/qdot3/montgomery#lib-modulo@0.1.0`
/// 
///      ```text
///      MIT License
/// 
///      Copyright (c) 2026 qdot3
/// 
///      Permission is hereby granted, free of charge, to any person obtaining a copy
///      of this software and associated documentation files (the "Software"), to deal
///      in the Software without restriction, including without limitation the rights
///      to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
///      copies of the Software, and to permit persons to whom the Software is
///      furnished to do so, subject to the following conditions:
/// 
///      The above copyright notice and this permission notice shall be included in all
///      copies or substantial portions of the Software.
/// 
///      THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
///      IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
///      FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
///      AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
///      LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
///      OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
///      SOFTWARE.
///      ```
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod npk_cp_lib {
    pub(crate) mod crates {
        pub mod lib_modulo {use std::ops::{Add,AddAssign,Mul,MulAssign,Neg,Sub,SubAssign};pub mod prime{use super::Context;const SMALL_TEST:u64={let mut test=0;let mut x=64;while x>0{x-=1;test=(test<<1)|if primality_test_naive(x){1}else{0};}test};static SET3:[u64;3]=[4230279247111683200,14694767155120705706,16641139526367750375,];static SET7:[u64;7]=[2,325,9375,28178,450775,9780504,1795265022];pub const fn primality_test(x:u64)->bool{if x<64{return(SMALL_TEST>>x)&1==1;}else if x%2==0||x%3==0||x%5==0||x%7==0{return false;}let(s,d)={let x=x-1;let s=x.trailing_zeros();(s-1,x>>s)};let ctx=Context::<u64>::new(x);let one=ctx.modulo(1).value;debug_assert!(one!=0,"gcd(r, n) = 1, r > 1, n > 1 => r % n != 0");let neg_one=x-one;let mut i=0;let witness=if x<350_269_456_337{SET3.as_slice()}else{SET7.as_slice()};'test:while i<witness.len(){let mut mint=ctx.modulo(witness[i]);i+=1;if mint.value==0{continue;}mint=mint.pow(d);if mint.value==one||mint.value==neg_one{continue;}let mut s=s;while s>0{s-=1;mint.value=mint.ctx.mul(mint.value,mint.value);if mint.value==neg_one{continue 'test;}}return false;}true}const fn primality_test_naive(x:u64)->bool{if x<2{return false;}let mut d=1;while d<x.isqrt(){d+=1;if x%d==0{return false;}}true}}pub type Context64=Context<u64>;pub type Context32=Context<u32>;pub type Modulo64<'a> =Modulo<'a,u64>;pub type Modulo32<'a> =Modulo<'a,u32>;#[derive(Debug,Clone,PartialEq,Eq,Hash)]pub struct Context<U>{n:U,inv_n:U,r2_mod_n:U,}#[derive(Debug,Clone,Copy,Hash)]pub struct Modulo<'a,U>{value:U,ctx:&'a Context<U>,}macro_rules!montgomery_impl{($single:ty,$double:ty)=>{impl Context<$single>{#[doc=" Calculates some parameters for Montgomery multiplication."]#[doc=""]#[doc=" # Panics"]#[doc=""]#[doc=" - modulus `n` should be an odd number."]pub const fn new(n:$single)->Self{assert!(n&1==1,"modulus should be an odd number");let inv_n={let mut inv_n=n%4;let mut d=const{<$single>::BITS.ilog2()-1};while d>0{inv_n=inv_n.wrapping_mul((2 as$single).wrapping_sub(n.wrapping_mul(inv_n)));d-=1;}debug_assert!(n.wrapping_mul(inv_n)==1);inv_n};let r2_mod_n=((n as$double).wrapping_neg()%(n as$double))as$single;Self{n,inv_n,r2_mod_n}}pub const fn modulo(&self,x:$single)->Modulo<'_,$single>{let x=self.mul(x,self.r2_mod_n);Modulo{value:x,ctx:&self,}}#[doc=" Performs Montgomery multiplication."]#[doc=""]#[doc=" if `lhs rhs < n r`, then `result < n`"]const fn mul(&self,lhs:$single,rhs:$single)->$single{let(x_hi,x_lo)={let x=lhs as$double*rhs as$double;((x>><$single>::BITS)as$single,x as$single)};let y_hi=((x_lo.wrapping_mul(self.inv_n)as$double*self.n as$double)>><$single>::BITS)as$single;let(z,b)=x_hi.overflowing_sub(y_hi);if b{z.wrapping_add(self.n)}else{z}}}impl<'a>Modulo<'a,$single>{#[doc=" Returns value."]pub const fn get(&self)->$single{self.ctx.mul(self.value,1)}#[doc=" Returns modulus."]pub const fn modulus(&self)->$single{self.ctx.n}#[doc=" Raises self to the power of `exp`, using exponentiation by squaring."]#[doc=""]#[doc=" # Time complexity"]#[doc=""]#[doc=" *O*(log *exp*)"]pub const fn pow(mut self,mut exp:$single)->Self{let mut result=self.ctx.modulo(1).value;while exp>0{if exp&1==1{result=self.ctx.mul(result,self.value)}exp>>=1;self.value=self.ctx.mul(self.value,self.value)}self.value=result;self}}impl<'a>Add for Modulo<'a,$single>{type Output=Self;fn add(mut self,rhs:Self)->Self{let(sum,b)=self.value.overflowing_add(rhs.value);self.value=if b||sum>=self.ctx.n{sum.wrapping_sub(self.ctx.n)}else{sum};self}}impl<'a>Sub for Modulo<'a,$single>{type Output=Self;fn sub(mut self,rhs:Self)->Self{let(diff,b)=self.value.overflowing_sub(rhs.value);self.value=if b{diff.wrapping_add(self.ctx.n)}else{diff};self}}impl<'a>Mul for Modulo<'a,$single>{type Output=Self;fn mul(mut self,rhs:Self)->Self{self.value=self.ctx.mul(self.value,rhs.value);self}}impl<'a>Neg for Modulo<'a,$single>{type Output=Self;fn neg(mut self)->Self::Output{self.value=if self.value==0{self.value}else{self.ctx.n-self.value};self}}};}montgomery_impl!(u64,u128);montgomery_impl!(u32,u64);impl<'a,U>AddAssign for Modulo<'a,U>where Self:Add<Output=Self>+Copy,{fn add_assign(&mut self,rhs:Self){*self=*self+rhs}}impl<'a,U>SubAssign for Modulo<'a,U>where Self:Sub<Output=Self>+Copy,{fn sub_assign(&mut self,rhs:Self){*self=*self-rhs}}impl<'a,U>MulAssign for Modulo<'a,U>where Self:Mul<Output=Self>+Copy,{fn mul_assign(&mut self,rhs:Self){*self=*self*rhs}}}
        pub mod from_bytes {use std::num::IntErrorKind;#[inline]const fn parse_8_digits(bytes:[u8;8])->Result<u64,IntErrorKind>{let mut n=u64::from_le_bytes(bytes)^0x3030_3030_3030_3030;if(n&0xf0f0_f0f0_f0f0_f0f0)|(n.wrapping_mul(7)&0x4040_4040_4040_4040)==0{n=(n.wrapping_mul((10<<8)+1)>>8)&0x00ff_00ff_00ff_00ff;n=(n.wrapping_mul((100<<16)+1)>>16)&0x0000_ffff_0000_ffff;n=n.wrapping_mul((10000<<32)+1)>>32;Ok(n)}else{Err(IntErrorKind::InvalidDigit)}}#[inline]const fn parse_4_digits(bytes:[u8;4])->Result<u32,IntErrorKind>{let mut n=u32::from_le_bytes(bytes)^0x3030_3030;if(n&0xf0f0_f0f0)|(n.wrapping_mul(7)&0x4040_4040)==0{n=(n.wrapping_mul((10<<8)+1)>>8)&0x00ff_00ff;n=n.wrapping_mul((100<<16)+1)>>16;Ok(n)}else{Err(IntErrorKind::InvalidDigit)}}pub trait FromBytes:Sized{type Err;fn from_bytes(bytes:&[u8])->Result<Self,Self::Err>;}macro_rules!parse_digits{($t:ty,$digits:expr,$mul:tt,$add:ident$(,$overflow:path)*)=>{{let(remainder,chunks)=$digits.as_rchunks::<8>();let mut n=0 as$t;if remainder.len()>4{let mut digits=[b'0';8];digits[8-remainder.len()..].copy_from_slice(remainder);n=n.$add(parse_8_digits(digits)?as$t)$(.ok_or($overflow)?)*;}else{let mut digits=[b'0';4];digits[4-remainder.len()..].copy_from_slice(remainder);n=n.$add(parse_4_digits(digits)?as$t)$(.ok_or($overflow)?)*;}for chunk in chunks{n=n.$mul(1_0000_0000)$(.ok_or($overflow)?)*;n=n.$add(parse_8_digits(*chunk)?as$t)$(.ok_or($overflow)?)*;}n}};}macro_rules!from_bytes_impl{($($t:ty)*)=>{$(impl FromBytes for$t{type Err=IntErrorKind;fn from_bytes(bytes:&[u8])->Result<Self,Self::Err>{if bytes.is_empty(){return Err(IntErrorKind::Empty);}#[allow(unused_comparisons)]let is_signed_ty=<$t>::MIN<0;let(is_positive,digits)=match bytes{[b'+'|b'-']=>return Err(IntErrorKind::InvalidDigit),[b'+',rest@..]=>(true,rest),[b'-',rest@..]if is_signed_ty=>(false,rest),_=>(true,bytes),};let never_overflow={const MAX_DIGITS_LEN:usize=<$t>::MAX.ilog10()as usize+1;const LEADING_BYTE_OF_MAX:u8=(<$t>::MAX/(10 as$t).pow(MAX_DIGITS_LEN as u32-1))as u8+b'0';(digits.len()<MAX_DIGITS_LEN)||(digits.len()==MAX_DIGITS_LEN&&digits[0]<LEADING_BYTE_OF_MAX)};let n=if never_overflow{if is_positive{parse_digits!($t,digits,wrapping_mul,wrapping_add)}else{parse_digits!($t,digits,wrapping_mul,wrapping_sub)}}else{if is_positive{parse_digits!($t,digits,checked_mul,checked_add,IntErrorKind::PosOverflow)}else{parse_digits!($t,digits,checked_mul,checked_sub,IntErrorKind::NegOverflow)}};Ok(n)}})*};}from_bytes_impl!(i32 u32 i64 u64 i128 u128 isize usize);macro_rules!from_bytes_impl_small_unsigned{($($t:ty)*)=>{$(impl FromBytes for$t{type Err=IntErrorKind;fn from_bytes(bytes:&[u8])->Result<Self,Self::Err>{let v=u32::from_bytes(bytes)?;if v><$t>::MAX as u32{Err(IntErrorKind::PosOverflow)}else{Ok(v as$t)}}})*};}from_bytes_impl_small_unsigned!(u8 u16);macro_rules!from_bytes_impl_small_signed{($($t:ty)*)=>{$(impl FromBytes for$t{type Err=IntErrorKind;fn from_bytes(bytes:&[u8])->Result<Self,Self::Err>{let v=i32::from_bytes(bytes)?;if v< <$t>::MIN as i32{Err(IntErrorKind::NegOverflow)}else if v><$t>::MAX as i32{Err(IntErrorKind::PosOverflow)}else{Ok(v as$t)}}})*};}from_bytes_impl_small_signed!(i8 i16);}
        pub mod input {use crate::npk_cp_lib::preludes::input::*;pub use crate::npk_cp_lib::macros::input::*;use std::io::{self,BufRead,ErrorKind};use from_bytes::FromBytes;pub struct FastInput<R>where R:BufRead,{reader:R,buf:Vec<u8>,}impl<R>FastInput<R>where R:BufRead,{#[inline]pub fn new(reader:R)->Self{Self{reader,buf:Vec::new(),}}pub fn next_token<T>(&mut self)->Option<T>where T:FromBytes,{{let buf=self.reader.fill_buf().ok()?;let i=buf.iter().take_while(|b|b.is_ascii_whitespace()).count();self.reader.consume(i);}let buf=self.reader.fill_buf().ok()?;if let Some(n)=buf.iter().position(|b|b.is_ascii_whitespace()){let token=T::from_bytes(&buf[..n]);self.reader.consume(n+1);token}else{let mut buf=std::mem::take(&mut self.buf);self.next_bytes(&mut buf).ok()?;let token=T::from_bytes(&buf);buf.clear();self.buf=buf;token}.ok()}pub fn next_token_vec<T>(&mut self,len:usize)->Option<Vec<T>>where T:FromBytes,{let mut vec=Vec::with_capacity(len);for _ in 0..len{vec.push(self.next_token()?)}Some(vec)}pub fn next_bytes(&mut self,buf:&mut Vec<u8>)->io::Result<()>{{let buf=self.reader.fill_buf()?;let i=buf.iter().take_while(|b|b.is_ascii_whitespace()).count();self.reader.consume(i);}loop{let available=match self.reader.fill_buf(){Ok(buf)=>buf,Err(e)if e.kind()==ErrorKind::Interrupted=>continue,Err(e)=>return Err(e),};let(done,used)=if let Some(n)=available.iter().position(|b|b.is_ascii_whitespace()){buf.extend_from_slice(&available[..n]);(true,n+1)}else{buf.extend_from_slice(&available);(false,available.len())};self.reader.consume(used);if done||(used==0){return Ok(());}}}}#[macro_export]macro_rules!npk_cp_lib_macro_def_input_parse{(@source[$source:ident]@rest$(,)?)=>{};(@source[$source:ident]@rest[$($item:tt)+]$(,)?)=>{$crate::npk_cp_lib::crates::input::parse!(@vec@source[$source]@item[$($item)+]@rest)};(@source[$source:ident]@rest($($item:tt)+)$(,)?)=>{$crate::npk_cp_lib::crates::input::parse!(@tuple@source[$source]@item[$($item)+]@rest)};(@source[$source:ident]@rest Bytes$(with capacity$len:expr)?$(,)?)=>{{let mut bytes=Vec::with_capacity(0$(+TryInto::<usize>::try_into($len).unwrap())?);$source.next_bytes(&mut bytes).unwrap();bytes}};(@source[$source:ident]@rest String$(with capacity$len:expr)?$(,)?)=>{{String::from_utf8($crate::npk_cp_lib::crates::input::parse!(@source[$source]@rest Bytes$(with capacity$len)?)).unwrap()}};(@source[$source:ident]@rest$item:ty$(,)?)=>{$source.next_token::<$item>().unwrap()};(@vec@source[$source:ident]@item[[$($item:tt)+];$len:expr]@rest)=>{(0..$len).into_iter().map(|_|$crate::npk_cp_lib::crates::input::parse!(@source[$source]@rest[$($item)+])).collect::<Vec<_>>()};(@vec@source[$source:ident]@item[($($item:tt)+);$len:expr]@rest)=>{(0..$len).into_iter().map(|_|$crate::npk_cp_lib::crates::input::parse!(@source[$source]@rest($($item)+))).collect::<Vec<_>>()};(@vec@source[$source:ident]@item[$item:tt;$len:expr]@rest)=>{(0..$len).into_iter().map(|_|$crate::npk_cp_lib::crates::input::parse!(@source[$source]@rest$item)).collect::<Vec<_>>()};(@tuple@source[$source:ident]@item[$($item:tt),+$(,)?]@rest)=>{($($crate::npk_cp_lib::crates::input::parse!(@source[$source]@rest$item),)+)};(@source[$source:ident]$($rest:tt)*)=>{std::compile_error!("failed to parse")};($source:ident>>$($rest:tt)*)=>{$crate::npk_cp_lib::crates::input::parse!(@source[$source]@rest$($rest)*)};}macro_rules!parse{($($tt:tt)*)=>(crate::npk_cp_lib_macro_def_input_parse!{$($tt)*})}#[macro_export]macro_rules!npk_cp_lib_macro_def_input_bind{(@source[$source:ident]@rest)=>{};(@source[$source:ident]@rest,$($rest:tt)*)=>{$crate::npk_cp_lib::crates::input::bind!(@source[$source]@rest$($rest)*)};(@source[$source:ident]@rest mut$($rest:tt)*)=>{$crate::npk_cp_lib::crates::input::bind!(@source[$source]@mut[mut]@rest$($rest)*)};(@source[$source:ident]@rest$($rest:tt)*)=>{$crate::npk_cp_lib::crates::input::bind!(@source[$source]@mut[]@rest$($rest)*)};(@source[$source:ident]@mut[$($mut:tt)?]@rest$ident:tt:$($rest:tt)*)=>{$crate::npk_cp_lib::crates::input::bind!(@source[$source]@mut[$($mut)?]@ident[$ident]@rest$($rest)*)};(@source[$source:ident]@mut[$($mut:tt)?]@ident[$ident:tt]@rest($($t:tt)+)$($rest:tt)*)=>{let$($mut)?$ident=$crate::npk_cp_lib::crates::input::parse!($source>>($($t)+));$crate::npk_cp_lib::crates::input::bind!(@source[$source]@rest$($rest)*)};(@source[$source:ident]@mut[$($mut:tt)?]@ident[$ident:tt]@rest[$($t:tt)+]$($rest:tt)*)=>{let$($mut)?$ident=$crate::npk_cp_lib::crates::input::parse!($source>>[$($t)+]);$crate::npk_cp_lib::crates::input::bind!(@source[$source]@rest$($rest)*)};(@source[$source:ident]@mut[$($mut:tt)?]@ident[$ident:tt]@rest$t:tt,$($rest:tt)*)=>{let$($mut)?$ident=$crate::npk_cp_lib::crates::input::parse!($source>>$t);$crate::npk_cp_lib::crates::input::bind!(@source[$source]@rest$($rest)*);};(@source[$source:ident]@mut[$($mut:tt)?]@ident[$ident:tt]@rest$t:tt)=>{let$($mut)?$ident=$crate::npk_cp_lib::crates::input::parse!($source>>$t);$crate::npk_cp_lib::crates::input::bind!(@source[$source]@rest);};(@source[$source:ident]$($rest:tt)*)=>{std::compile_error!("failed to parse")};($source:ident>>$($rest:tt)*)=>{$crate::npk_cp_lib::crates::input::bind!(@source[$source]@rest$($rest)*)};}macro_rules!bind{($($tt:tt)*)=>(crate::npk_cp_lib_macro_def_input_bind!{$($tt)*})}}
    }

    pub(crate) mod macros {
        pub mod lib_modulo {}
        pub mod from_bytes {}
        pub mod input {pub use crate::{npk_cp_lib_macro_def_input_bind as bind,npk_cp_lib_macro_def_input_parse as parse};}
    }

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

    mod preludes {
        pub mod lib_modulo {}
        pub mod from_bytes {}
        pub mod input {pub(in crate::npk_cp_lib)use crate::npk_cp_lib::crates::from_bytes;}
    }
}
0