結果
| 問題 | No.8030 ミラー・ラビン素数判定法のテスト |
| ユーザー |
 nPk
|
| 提出日時 | 2026-04-14 19:13:55 |
| 言語 | Rust (1.94.0 + proconio + num + itertools) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 12,626 bytes |
| 記録 | |
| コンパイル時間 | 3,057 ms |
| コンパイル使用メモリ | 212,592 KB |
| 実行使用メモリ | 6,400 KB |
| 最終ジャッジ日時 | 2026-04-14 19:14:09 |
| 合計ジャッジ時間 | 4,542 ms |
|
ジャッジサーバーID （参考情報） |
judge2_0 / judge3_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | WA * 10 |
ソースコード
pub use npk_cp_lib::prelude::*;
use std::{io::stdin, num::NonZeroU64};
use input::{bind, FastInput};
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")
}
}
}
struct Divisor64 {
d: u64,
/// `(1 << 128).div_ceil(d)`
r: u128,
}
impl Divisor64 {
const fn new(d: NonZeroU64) -> Self {
let d = d.get();
let r = !0 / d as u128 + 1;
Self { d, r }
}
#[inline(always)]
const fn modulo(&self, x: u128) -> u64 {
let (hi, lo) = {
let x = self.r.wrapping_mul(x as u128).wrapping_mul(self.d as u128);
(x >> 64, x & (!0 >> 64))
};
(hi.wrapping_mul(self.d as u128)
.wrapping_add((lo * self.d as u128) >> 64)
>> 64) as u64
}
#[inline(always)]
const fn pow(&self, mut x: u64, mut exp: u64) -> u64 {
let mut res = 1;
while exp > 0 {
if exp & 1 == 1 {
res = self.modulo(res as u128 * x as u128);
}
exp >>= 1;
x = self.modulo(x as u128 * x as u128)
}
res
}
}
// from <https://miller-rabin.appspot.com/>
/// x < 350_269_456_337
static SET3: [u64; 3] = [
4230279247111683200,
14694767155120705706,
16641139526367750375,
];
/// x < 2^64
static SET7: [u64; 7] = [2, 325, 9375, 28178, 450775, 9780504, 1795265022];
/// Performs deterministic Miller-Rabin primality test.
///
/// # Time complexity
///
/// *O*(log *x*)
pub const fn primality_test(x: u64) -> bool {
/// `x` is prime iff `(test >> x) & 1 == 1`
const SMALL_PRIME: 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
};
/// remove multiples of 2, 3 or 5
const MAY_BE_PRIME_30: u32 = {
let mut table = 0;
let mut n = 0;
while n < 30 {
table |= if n % 2 == 0 || n % 3 == 0 || n % 5 == 0 {
0 // composite
} else {
1 // may be prime
} << n;
n += 1;
}
table
};
if x < 64 {
return (SMALL_PRIME >> x) & 1 == 1;
} else if (MAY_BE_PRIME_30 >> x % 30) & 1 == 0 || x % 7 == 0 {
return false;
}
let (s, d) = {
let x = x - 1;
let s = x.trailing_zeros();
(s - 1, x >> s)
};
let divisor = Divisor64::new(NonZeroU64::new(x).unwrap());
let witness = if x < 350_269_456_337 {
SET3.as_slice()
} else {
SET7.as_slice()
};
let mut i = 0;
'test: while i < witness.len() {
let mut w = divisor.modulo(witness[i] as u128);
i += 1;
if w == 0 {
continue;
}
w = divisor.pow(w, d);
if w == 1 || w == x - 1 {
continue;
}
let mut s = s;
while s > 0 {
s -= 1;
w = divisor.modulo(w as u128 * w as u128);
if w == x - 1 {
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
}
// The following code was expanded by `cargo-equip`.
/// # Bundled libraries
///
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod npk_cp_lib {
pub(crate) mod crates {
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 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 from_bytes {}
pub mod input {pub(in crate::npk_cp_lib)use crate::npk_cp_lib::crates::from_bytes;}
}
}