結果
| 問題 |
No.8030 ミラー・ラビン素数判定法のテスト
|
| ユーザー |
 katand
|
| 提出日時 | 2022-09-23 13:20:23 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 32 ms / 9,973 ms |
| コード長 | 12,925 bytes |
| コンパイル時間 | 14,432 ms |
| コンパイル使用メモリ | 383,420 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-12-22 05:15:23 |
| 合計ジャッジ時間 | 16,122 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 10 |
ソースコード
pub struct Writer<W: Write> {
writer: BufWriter<W>,
}
impl<W: Write> Writer<W> {
pub fn new(write: W) -> Self {
Self {
writer: BufWriter::new(write),
}
}
pub fn ln<S: Display>(&mut self, s: S) {
writeln!(self.writer, "{}", s).expect("Failed to write.")
}
pub fn out<S: Display>(&mut self, s: S) {
write!(self.writer, "{}", s).expect("Failed to write.")
}
pub fn join<S: Display>(&mut self, v: &[S], separator: &str) {
v.iter().fold("", |sep, arg| {
write!(self.writer, "{}{}", sep, arg).expect("Failed to write.");
separator
});
writeln!(self.writer).expect("Failed to write.");
}
pub fn bits(&mut self, i: i64, len: usize) {
(0..len).for_each(|b| write!(self.writer, "{}", i >> b & 1).expect("Failed to write."));
writeln!(self.writer).expect("Failed to write.")
}
pub fn flush(&mut self) {
let _ = self.writer.flush();
}
}
pub struct Reader<F> {
init: F,
buf: VecDeque<String>,
}
impl<R: BufRead, F: FnMut() -> R> Iterator for Reader<F> {
type Item = String;
fn next(&mut self) -> Option<String> {
if self.buf.is_empty() {
let mut reader = (self.init)();
let mut l = String::new();
reader.read_line(&mut l).unwrap();
self.buf
.append(&mut l.split_whitespace().map(ToString::to_string).collect());
}
self.buf.pop_front()
}
}
impl<R: BufRead, F: FnMut() -> R> Reader<F> {
pub fn new(init: F) -> Self {
let buf = VecDeque::new();
Reader { init, buf }
}
pub fn v<T: FS>(&mut self) -> T {
let s = self.next().expect("Insufficient input.");
s.parse().ok().expect("Failed to parse.")
}
pub fn v2<T1: FS, T2: FS>(&mut self) -> (T1, T2) {
(self.v(), self.v())
}
pub fn v3<T1: FS, T2: FS, T3: FS>(&mut self) -> (T1, T2, T3) {
(self.v(), self.v(), self.v())
}
pub fn v4<T1: FS, T2: FS, T3: FS, T4: FS>(&mut self) -> (T1, T2, T3, T4) {
(self.v(), self.v(), self.v(), self.v())
}
pub fn v5<T1: FS, T2: FS, T3: FS, T4: FS, T5: FS>(&mut self) -> (T1, T2, T3, T4, T5) {
(self.v(), self.v(), self.v(), self.v(), self.v())
}
pub fn vec<T: FS>(&mut self, length: usize) -> Vec<T> {
(0..length).map(|_| self.v()).collect()
}
pub fn vec2<T1: FS, T2: FS>(&mut self, length: usize) -> Vec<(T1, T2)> {
(0..length).map(|_| self.v2()).collect()
}
pub fn vec3<T1: FS, T2: FS, T3: FS>(&mut self, length: usize) -> Vec<(T1, T2, T3)> {
(0..length).map(|_| self.v3()).collect()
}
pub fn vec4<T1: FS, T2: FS, T3: FS, T4: FS>(&mut self, length: usize) -> Vec<(T1, T2, T3, T4)> {
(0..length).map(|_| self.v4()).collect()
}
pub fn chars(&mut self) -> Vec<char> {
self.v::<String>().chars().collect()
}
fn split(&mut self, zero: u8) -> Vec<usize> {
self.v::<String>()
.chars()
.map(|c| (c as u8 - zero) as usize)
.collect()
}
pub fn digits(&mut self) -> Vec<usize> {
self.split(b'0')
}
pub fn lowercase(&mut self) -> Vec<usize> {
self.split(b'a')
}
pub fn uppercase(&mut self) -> Vec<usize> {
self.split(b'A')
}
pub fn char_map(&mut self, h: usize) -> Vec<Vec<char>> {
(0..h).map(|_| self.chars()).collect()
}
pub fn bool_map(&mut self, h: usize, ng: char) -> Vec<Vec<bool>> {
self.char_map(h)
.iter()
.map(|v| v.iter().map(|&c| c != ng).collect())
.collect()
}
pub fn matrix<T: FS>(&mut self, h: usize, w: usize) -> Vec<Vec<T>> {
(0..h).map(|_| self.vec(w)).collect()
}
}
pub fn to_lr<T, R: RangeBounds<T>>(range: &R, length: T) -> (T, T)
where
T: Copy + One + Zero + Add<Output = T> + PartialOrd,
{
use Bound::{Excluded, Included, Unbounded};
let l = match range.start_bound() {
Unbounded => T::zero(),
Included(&s) => s,
Excluded(&s) => s + T::one(),
};
let r = match range.end_bound() {
Unbounded => length,
Included(&e) => e + T::one(),
Excluded(&e) => e,
};
assert!(l <= r && r <= length);
(l, r)
}
pub use std::{
cmp::{max, min, Ordering, Reverse},
collections::{
hash_map::RandomState, BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque,
},
convert::Infallible,
convert::{TryFrom, TryInto},
fmt::{Debug, Display, Formatter},
hash::Hash,
io::{stdin, stdout, BufRead, BufWriter, Read, Write},
iter::{repeat, Product, Sum},
marker::PhantomData,
mem::swap,
ops::{
Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Bound,
Deref, DerefMut, Div, DivAssign, Index, IndexMut, Mul, MulAssign, Neg, Not, Range,
RangeBounds, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign, Sub, SubAssign,
},
str::{from_utf8, FromStr as FS},
};
#[allow(unused_macros)]
macro_rules ! chmax {($ base : expr , $ ($ cmps : expr ) ,+ $ (, ) * ) => {{let cmp_max = max ! ($ ($ cmps ) ,+ ) ; if $ base < cmp_max {$ base = cmp_max ; true } else {false } } } ; }
#[allow(unused_macros)]
macro_rules ! max {($ a : expr $ (, ) * ) => {{$ a } } ; ($ a : expr , $ b : expr $ (, ) * ) => {{if $ a > $ b {$ a } else {$ b } } } ; ($ a : expr , $ ($ rest : expr ) ,+ $ (, ) * ) => {{let b = max ! ($ ($ rest ) ,+ ) ; if $ a > b {$ a } else {b } } } ; }
#[allow(unused_macros)]
macro_rules ! chmin {($ base : expr , $ ($ cmps : expr ) ,+ $ (, ) * ) => {{let cmp_min = min ! ($ ($ cmps ) ,+ ) ; if $ base > cmp_min {$ base = cmp_min ; true } else {false } } } ; }
#[allow(unused_macros)]
macro_rules ! min {($ a : expr $ (, ) * ) => {{$ a } } ; ($ a : expr , $ b : expr $ (, ) * ) => {{if $ a > $ b {$ b } else {$ a } } } ; ($ a : expr , $ ($ rest : expr ) ,+ $ (, ) * ) => {{let b = min ! ($ ($ rest ) ,+ ) ; if $ a > b {b } else {$ a } } } ; }
#[allow(unused_macros)]
macro_rules ! chmax {($ base : expr , $ ($ cmps : expr ) ,+ $ (, ) * ) => {{let cmp_max = max ! ($ ($ cmps ) ,+ ) ; if $ base < cmp_max {$ base = cmp_max ; true } else {false } } } ; }
#[allow(unused_macros)]
macro_rules ! max {($ a : expr $ (, ) * ) => {{$ a } } ; ($ a : expr , $ b : expr $ (, ) * ) => {{if $ a > $ b {$ a } else {$ b } } } ; ($ a : expr , $ ($ rest : expr ) ,+ $ (, ) * ) => {{let b = max ! ($ ($ rest ) ,+ ) ; if $ a > b {$ a } else {b } } } ; }
pub trait Magma {
type M: Clone + PartialEq + Debug;
fn op(x: &Self::M, y: &Self::M) -> Self::M;
}
pub trait Associative {}
pub trait Unital: Magma {
fn unit() -> Self::M;
}
pub trait Commutative: Magma {}
pub trait Invertible: Magma {
fn inv(x: &Self::M) -> Self::M;
}
pub trait Idempotent: Magma {}
pub trait SemiGroup: Magma + Associative {}
pub trait Monoid: Magma + Associative + Unital {
fn pow(&self, x: Self::M, mut n: usize) -> Self::M {
let mut res = Self::unit();
let mut base = x;
while n > 0 {
if n & 1 == 1 {
res = Self::op(&res, &base);
}
base = Self::op(&base, &base);
n >>= 1;
}
res
}
}
impl<M: Magma + Associative + Unital> Monoid for M {}
pub trait CommutativeMonoid: Magma + Associative + Unital + Commutative {}
impl<M: Magma + Associative + Unital + Commutative> CommutativeMonoid for M {}
pub trait Group: Magma + Associative + Unital + Invertible {}
impl<M: Magma + Associative + Unital + Invertible> Group for M {}
pub trait AbelianGroup: Magma + Associative + Unital + Commutative + Invertible {}
impl<M: Magma + Associative + Unital + Commutative + Invertible> AbelianGroup for M {}
pub trait Band: Magma + Associative + Idempotent {}
impl<M: Magma + Associative + Idempotent> Band for M {}
pub trait MapMonoid {
type Mono: Monoid;
type Func: Monoid;
fn op(
&self,
x: &<Self::Mono as Magma>::M,
y: &<Self::Mono as Magma>::M,
) -> <Self::Mono as Magma>::M {
Self::Mono::op(x, y)
}
fn unit() -> <Self::Mono as Magma>::M {
Self::Mono::unit()
}
fn apply(
&self,
f: &<Self::Func as Magma>::M,
value: &<Self::Mono as Magma>::M,
) -> <Self::Mono as Magma>::M;
fn identity_map() -> <Self::Func as Magma>::M {
Self::Func::unit()
}
fn compose(
&self,
f: &<Self::Func as Magma>::M,
g: &<Self::Func as Magma>::M,
) -> <Self::Func as Magma>::M {
Self::Func::op(f, g)
}
}
pub trait Zero {
fn zero() -> Self;
}
pub trait One {
fn one() -> Self;
}
pub trait BoundedBelow {
fn min_value() -> Self;
}
pub trait BoundedAbove {
fn max_value() -> Self;
}
# [rustfmt :: skip ] pub trait Integral : 'static + Send + Sync + Copy + Ord + Display + Debug + Add < Output = Self > + Sub < Output = Self > + Mul < Output = Self > + Div < Output = Self > + Rem < Output = Self > + AddAssign + SubAssign + MulAssign + DivAssign + RemAssign + Sum + Product + BitOr < Output = Self > + BitAnd < Output = Self > + BitXor < Output = Self > + Not < Output = Self > + Shl < Output = Self > + Shr < Output = Self > + BitOrAssign + BitAndAssign + BitXorAssign + ShlAssign + ShrAssign + Zero + One + BoundedBelow + BoundedAbove {}
macro_rules ! impl_integral {($ ($ ty : ty ) ,* ) => {$ (impl Zero for $ ty {fn zero () -> Self {0 } } impl One for $ ty {fn one () -> Self {1 } } impl BoundedBelow for $ ty {fn min_value () -> Self {Self :: min_value () } } impl BoundedAbove for $ ty {fn max_value () -> Self {Self :: max_value () } } impl Integral for $ ty {} ) * } ; }
impl_integral!(i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize);
pub fn main() {
let stdin = stdin();
let stdout = stdout();
solve(Reader::new(|| stdin.lock()), Writer::new(stdout.lock()));
}
pub trait MillerRabin {
fn is_prime(&self) -> bool;
}
impl MillerRabin for u64 {
fn is_prime(&self) -> bool {
if *self < 2 || *self & 1 == 0 {
return *self == 2;
}
let mont = MontgomeryU64::new(*self);
let is_composite = |mut checker: u64| -> bool {
if checker >= *self {
checker %= self;
}
if checker == 0 {
return false;
}
let mut tr = mont.pow(mont.ar(checker), mont.d);
if tr == mont.r || tr == mont.rn {
return false;
}
(1..mont.k).all(|_| {
tr = mont.mrmul(tr, tr);
tr != mont.rn
})
};
vec![
vec![2, 7, 61],
vec![2, 325, 9375, 28178, 450775, 9780504, 1795265022],
][if *self < 1 << 32 { 0 } else { 1 }]
.iter()
.all(|&checker| !is_composite(checker))
}
}
#[derive(Clone, Debug)]
pub struct MontgomeryU64 {
pub n: u64,
pub ni: u64,
pub nh: u64,
pub r: u64,
pub rn: u64,
pub r2: u64,
pub d: u64,
pub k: u32,
}
impl MontgomeryU64 {
#[inline]
pub fn new(n: u64) -> Self {
debug_assert_eq!(n & 1, 1);
let ni = (0..5).fold(n, |x, _a| {
x.wrapping_mul(2u64.wrapping_sub(n.wrapping_mul(x)))
});
debug_assert_eq!(n.wrapping_mul(ni), 1);
let nh = (n >> 1) + 1;
let r = n.wrapping_neg() % n;
let rn = n - r;
let r2 = ((n as u128).wrapping_neg() % (n as u128)) as u64;
let k = (n - 1).trailing_zeros();
let d = (n - 1) >> k;
Self {
n,
ni,
nh,
r,
rn,
r2,
d,
k,
}
}
#[inline]
pub fn ar(&self, a: u64) -> u64 {
debug_assert!(a < self.n);
self.mrmul(a, self.r2)
}
#[inline]
pub fn mrmul(&self, ar: u64, br: u64) -> u64 {
debug_assert!(ar < self.n);
debug_assert!(br < self.n);
let t: u128 = (ar as u128) * (br as u128);
let (t, f) = ((t >> 64) as u64).overflowing_sub(
((((t as u64).wrapping_mul(self.ni) as u128) * self.n as u128) >> 64) as u64,
);
if f {
t.wrapping_add(self.n)
} else {
t
}
}
#[inline]
pub fn pow(&self, mut ar: u64, mut b: u64) -> u64 {
debug_assert!(ar < self.n);
let mut t = if b & 1 == 0 { self.r } else { ar };
b >>= 1;
while b != 0 {
ar = self.mrmul(ar, ar);
if b & 1 != 0 {
t = self.mrmul(t, ar);
}
b >>= 1;
}
t
}
}
pub fn solve<R: BufRead, W: Write, F: FnMut() -> R>(mut reader: Reader<F>, mut writer: Writer<W>) {
let n: u64 = reader.v();
for _ in 0..n {
let x = reader.v::<u64>();
writer.ln(format!("{} {}", x, if x.is_prime() { "1" } else { "0" }));
}
}