結果
| 問題 | No.8030 ミラー・ラビン素数判定法のテスト |
| ユーザー |
 nPk
|
| 提出日時 | 2026-04-05 01:27:52 |
| 言語 | Rust (1.94.0 + proconio + num + itertools) |
| 結果 |
AC
|
| 実行時間 | 38 ms / 9,973 ms |
| コード長 | 16,978 bytes |
| 記録 | |
| コンパイル時間 | 11,956 ms |
| コンパイル使用メモリ | 211,664 KB |
| 実行使用メモリ | 6,400 KB |
| 最終ジャッジ日時 | 2026-04-05 01:28:08 |
| 合計ジャッジ時間 | 3,686 ms |
|
ジャッジサーバーID （参考情報） |
judge3_1 / judge1_0 |
| 純コード判定待ち |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 10 |
ソースコード
pub use npk_cp_lib::prelude::*;
use std::io::stdin;
use input::{bind, FastInput};
use montgomery_uint::Montgomery64;
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 Montgomery64::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#montgomery-uint@0.1.0` licensed under `Apache-2.0 OR MIT` as `crate::npk_cp_lib::crates::montgomery_uint`
///
/// # License and Copyright Notices
///
/// - `git+https://github.com/qdot3/montgomery#montgomery-uint@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 montgomery_uint {use std::ops::{Add,AddAssign,Mul,MulAssign,Neg,Sub,SubAssign};macro_rules!montgomery_primitive_impl{($factory:tt,$mint:tt,$small:ty,$large:ty,$mr_set:expr,)=>{#[doc=concat!("Factory to produce [",stringify!($mint),"].")]#[derive(Debug,Clone,PartialEq,Eq,Hash)]pub struct$factory{n:$large,nn:$large,r2:$large,}impl$factory{#[doc=" # Panic"]#[doc=""]#[doc=" `n` should be a odd number."]#[doc=""]#[doc=" # Example"]#[doc=""]#[doc=" ```"]#[doc=concat!("use montgomery_uint::",stringify!($factory)," as Montgomery;")]#[doc=""]#[doc=" const FACTORY: Montgomery = Montgomery::new(101);"]#[doc=""]#[doc=" let modulus = 103;"]#[doc=" let factory = Montgomery::new(modulus);"]#[doc=" ```"]pub const fn new(n:$small)->Self{assert!(n&1==1,"modulus should be odd number");let nn={let mut nn:$small=n.wrapping_neg()%4;let mut d=<$small>::BITS.ilog2()-1;while d>0{d-=1;nn=nn.wrapping_mul(n.wrapping_mul(nn).wrapping_add(2));}debug_assert!(n.wrapping_mul(nn).wrapping_add(1)==0,"n * nn = -1 (mod 2^32)");nn as$large};let n=n as$large;let r2=n.wrapping_neg()%n;Self{n,nn,r2}}#[doc=" # Example"]#[doc=""]#[doc=" ```"]#[doc=concat!("use montgomery_uint::",stringify!($factory)," as Montgomery;")]#[doc=""]#[doc=" let factory = Montgomery::new(99);"]#[doc=" let mint_100 = factory.new_mint(4) * factory.new_mint(25);"]#[doc=" assert_eq!(mint_100.get(), 1);"]#[doc=" ```"]pub const fn new_mint(&self,x:$large)->$mint<'_>{let x=if x>=self.n{x%self.n}else{x}*self.r2;let value=self.reduce(x);$mint{value,ctx:&self}}#[doc=" Performs Montgomery reduction."]#[doc=""]#[doc=" If `x` < `n r`, then returned value will be less than `n`"]const fn reduce(&self,x:$large)->$large{const MASK:$large=<$small>::MAX as$large;let m=((x&MASK)*self.nn&MASK)*self.n;let t=(x/2+m/2+1)>><$small>::BITS-1;if t>=self.n{t-self.n}else{t}}#[doc=" Performs deterministic Miller-Rabin primality test."]#[doc=""]#[doc=" # Time Complexity"]#[doc=""]#[doc=" *O*(log *x*)"]#[doc=""]#[doc=" # Example"]#[doc=""]#[doc=" ```"]#[doc=concat!("use montgomery_uint::",stringify!($factory)," as Montgomery;")]#[doc=""]#[doc=" // composite numbers"]#[doc=" for n in [0, 1, 4, 6, 8, 9, !0] {"]#[doc=" assert!(!Montgomery::primality_test(n));"]#[doc=" }"]#[doc=" // prime numbers"]#[doc=" for n in [2, 3, 5, 7, 10_007, 998_244_353] {"]#[doc=" assert!(Montgomery::primality_test(n));"]#[doc=" }"]#[doc=" ```"]pub const fn primality_test(x:$small)->bool{if x&1==0{return x==2;}else if x==1{return false;}let(s,d)={let x=x-1;let s=x.trailing_zeros();(s-1,x>>s)};let factory=<$factory>::new(x);let one=factory.new_mint(1).value;let neg_one=factory.new_mint(x as$large-1).value;let mut i=0;let a=const{$mr_set};'test:while i<a.len(){let mut mint=factory.new_mint(a[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.reduce(mint.value*mint.value);if mint.value==neg_one{continue 'test;}}return false;}true}}#[doc=" Unsigned integer in Montgomery representation."]#[doc=""]#[doc=concat!("Two [",stringify!($mint),"]s with different modulus can interact but the results will be useless. Using block to drop [",stringify!($factory),"] is recommended")]#[derive(Debug,Clone,Copy,Hash,PartialEq,Eq)]pub struct$mint<'a>{value:$large,ctx:&'a$factory,}impl<'a>$mint<'a>{#[doc=" Returns modulus."]#[doc=""]#[doc=" # Example"]#[doc=""]#[doc=" ```"]#[doc=concat!("use montgomery_uint::",stringify!($factory)," as Montgomery;")]#[doc=""]#[doc=" let factory = Montgomery::new(99);"]#[doc=" for i in 0..1000 {"]#[doc=" assert_eq!(factory.new_mint(i).modulus(), 99);"]#[doc=" }"]#[doc=" ```"]pub const fn modulus(&self)->$small{self.ctx.n as$small}#[doc=" Returns value."]#[doc=""]#[doc=" # Example"]#[doc=""]#[doc=" ```"]#[doc=concat!("use montgomery_uint::",stringify!($factory)," as Montgomery;")]#[doc=""]#[doc=" let factory = Montgomery::new(11);"]#[doc=" let mint = factory.new_mint(11 * 100 + 7);"]#[doc=""]#[doc=" assert_eq!(mint.get(), 7);"]#[doc=" ```"]pub const fn get(&self)->$small{self.ctx.reduce(self.value)as$small}#[doc=" # Time Complexity"]#[doc=""]#[doc=" *O*(log `exp`)"]#[doc=""]#[doc=" # Example"]#[doc=""]#[doc=" ```"]#[doc=concat!("use montgomery_uint::",stringify!($factory)," as Montgomery;")]#[doc=""]#[doc=" let n = 10001;"]#[doc=" let mut pow2 = 1;"]#[doc=""]#[doc=" let factory = Montgomery::new(n);"]#[doc=" let mint = factory.new_mint(3);"]#[doc=""]#[doc=" for d in 1..1000 {"]#[doc=" pow2 = pow2 * 3 % n;"]#[doc=""]#[doc=" assert_eq!(mint.pow(d).get(), pow2)"]#[doc=" }"]#[doc=" ```"]pub const fn pow(mut self,mut exp:$small)->Self{let mut res=self.ctx.reduce(self.ctx.r2);while exp>0{if exp&1==1{res=self.ctx.reduce(res*self.value);}exp>>=1;self.value=self.ctx.reduce(self.value*self.value);}self.value=res;self}}impl<'a>Add for$mint<'a>{type Output=Self;fn add(mut self,rhs:Self)->Self::Output{self.value+=rhs.value;if self.value>=self.ctx.n{self.value-=self.ctx.n}self}}impl<'a>AddAssign for$mint<'a>{fn add_assign(&mut self,rhs:Self){*self=*self+rhs}}impl<'a>Sub for$mint<'a>{type Output=Self;fn sub(mut self,rhs:Self)->Self::Output{self.value=self.value.wrapping_sub(rhs.value);if self.value>=self.ctx.n{self.value=self.value.wrapping_add(self.ctx.n)}self}}impl<'a>SubAssign for$mint<'a>{fn sub_assign(&mut self,rhs:Self){*self=*self-rhs}}impl<'a>Mul for$mint<'a>{type Output=Self;fn mul(mut self,rhs:Self)->Self::Output{self.value=self.ctx.reduce(self.value*rhs.value);self}}impl<'a>MulAssign for$mint<'a>{fn mul_assign(&mut self,rhs:Self){*self=*self*rhs}}impl<'a>Neg for$mint<'a>{type Output=Self;fn neg(mut self)->Self::Output{if self.value>0{self.value=self.ctx.n-self.value}self}}};}montgomery_primitive_impl!(Montgomery32,Mint32,u32,u64,[2,3,61],);montgomery_primitive_impl!(Montgomery64,Mint64,u64,u128,[2,325,9375,28178,450775,9780504,1795265022],);}
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 montgomery_uint {}
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 montgomery_uint {}
pub mod from_bytes {}
pub mod input {pub(in crate::npk_cp_lib)use crate::npk_cp_lib::crates::from_bytes;}
}
}