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

• 問題: No.3030 ミラー・ラビン素数判定法のテスト
• ユーザー: Haar
• 提出日時: 2021-09-23 22:51:44
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 348 ms / 9,973 ms
• コード長: 5,116 bytes
• コンパイル時間: 12,837 ms
• コンパイル使用メモリ: 378,732 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-04-28 09:45:43
• 合計ジャッジ時間: 14,497 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	181 ms; 5,376 KB
testcase_05	AC	171 ms; 5,376 KB
testcase_06	AC	46 ms; 5,376 KB
testcase_07	AC	44 ms; 5,376 KB
testcase_08	AC	48 ms; 5,376 KB
testcase_09	AC	348 ms; 5,376 KB

コンパイルメッセージ

warning: lint `redundant_semicolon` has been renamed to `redundant_semicolons`
  --> src/main.rs:67:37
   |
67 |             #[allow(non_snake_case, redundant_semicolon)]
   |                                     ^^^^^^^^^^^^^^^^^^^ help: use the new name: `redundant_semicolons`
...
83 | impl_join_str_tuple!(T0, T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11);
   | ---------------------------------------------------------------------- in this macro invocation
   |
   = note: `#[warn(renamed_and_removed_lints)]` on by default
   = note: this warning originates in the macro `impl_join_str_tuple` (in Nightly builds, run with -Z macro-backtrace for more info)

warning: lint `redundant_semicolon` has been renamed to `redundant_semicolons`
  --> src/main.rs:67:37
   |
67 |             #[allow(non_snake_case, redundant_semicolon)]
   |                                     ^^^^^^^^^^^^^^^^^^^ help: use the new name: `redundant_semicolons`
...
83 | impl_join_str_tuple!(T0, T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11);
   | ---------------------------------------------------------------------- in this macro invocation
   |
   = note: this warning originates in the macro `impl_join_str_tuple` (in Nightly builds, run with -Z macro-backtrace for more info)

ソースコード

#[allow(unused_imports)]
use std::io::{Read, Write};

#[allow(unused_macros)]
macro_rules! get {
    ( $in:ident, [$a:tt; $num:expr] ) => {
        {
            let n = $num;
            (0 .. n).map(|_| get!($in, $a)).collect::<Vec<_>>()
        }
    };

    ( $in:ident, ($($type:ty),*) ) => {
        ($(get!($in, $type)),*)
    };

    ( $in:ident, $type:ty ) => {
        {
            let token = $in.next().unwrap();

            token.parse::<$type>().expect(
                format!("cannot convert \"{}\" into {}", token, stringify!($type)).as_str()
            )
        }
    };
}

#[allow(unused_macros)]
macro_rules! input {
    ( @inner $in:ident, mut $name:ident : $type:tt ) => {
        let mut $name = get!($in, $type);
    };

    ( @inner $in:ident, $name:ident : $type:tt ) => {
        let $name = get!($in, $type);
    };

    ( $in:ident, $($($names:ident)* : $type:tt),* ) => {
        $(
            input!(@inner $in, $($names)* : $type);
        )*
    }
}

pub trait JoinStr {
    fn join_str(&self, _: &str) -> String;
}

impl<T: std::fmt::Display> JoinStr for Vec<T> {
    fn join_str(&self, s: &str) -> String {
        (&self.iter().map(|x| format!("{}", x)).collect::<Vec<_>>()).join(s)
    }
}

macro_rules! impl_join_str_tuple {
    ( $head:ident ) => {
        impl<$head: std::fmt::Display> JoinStr for ($head,) {
            #[allow(non_snake_case, redundant_semicolons)]
            fn join_str(&self, _: &str) -> String {
                let (ref $head,) = *self;
                format!("{}", $head)
            }
        }
    };
    ( $head:ident, $($tail:ident),+ ) => {
        impl<$head: std::fmt::Display, $($tail: std::fmt::Display),+> JoinStr for ($head, $($tail),*) {
            #[allow(non_snake_case, redundant_semicolon)]
            fn join_str(&self, s: &str) -> String {
                let mut ret = vec![];
                let (ref $head, $(ref $tail,)+) = *self;
                ret.push(format!("{}", $head));
                $(
                    ret.push(format!("{}", $tail));
                )+;
                ret.join_str(s)
            }
        }

        impl_join_str_tuple!($($tail),+);
    }
}

impl_join_str_tuple!(T0, T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11);

#[allow(unused_macros)]
macro_rules! io {
    ( $in:ident, $out:ident ) => {
        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        let mut $in = s.split_ascii_whitespace();

        let $out = std::io::stdout();
        let mut $out = std::io::BufWriter::new($out.lock());
    };
}

#[macro_export]
macro_rules! mul_vec {
    ( $v:expr; $n:expr ) => {
        vec![$v; $n]
    };

    ( $v:expr; $n:expr, $($ns:expr),+ ) => {
        vec![mul_vec![$v; $($ns),+]; $n]
    }
}

pub mod main {
    use super::*;
    use haar_lib::math::miller_rabin::*;

    #[derive(Clone, Default)]
    pub struct Problem {/* write variables here */}

    impl Problem {
        pub fn main(&mut self) -> Result<(), Box<dyn std::error::Error>> {
            io!(cin, cout);

            input!(cin, n: usize, xs: [u64; n]);

            for x in xs {
                writeln!(cout, "{} {}", x, if miller_rabin(x) { 1 } else { 0 })?;
            }

            Ok(())
        }
        /* write functions here */
    }
}

fn main() {
    main::Problem::default().main().unwrap();
}

use crate as haar_lib;
pub mod math {
    pub mod miller_rabin {
        fn pow(mut a: u128, mut b: u128, p: u128) -> u128 {
            let mut ret = 1;
            while b > 0 {
                if b & 1 == 1 {
                    ret = ret * a % p;
                }
                a = a * a % p;
                b >>= 1;
            }
            ret
        }

        fn is_composite(a: u64, p: u64, s: u64, d: u64) -> bool {
            let p = p as u128;
            let mut x = pow(a as u128, d as u128, p);
            if x == 1 {
                false
            } else {
                for _ in 0..s {
                    if x == p - 1 {
                        return false;
                    }
                    x = x * x % p;
                }
                true
            }
        }

        pub fn miller_rabin(n: u64) -> bool {
            if n <= 1 {
                false
            } else if n == 2 {
                true
            } else if n % 2 == 0 {
                false
            } else {
                let mut s = 0;
                let mut d = n - 1;
                while d & 1 == 0 {
                    s += 1;
                    d >>= 1;
                }
                if n < 4759123141 {
                    for &x in &[2, 7, 61] {
                        if x < n && is_composite(x, n, s, d) {
                            return false;
                        }
                    }
                    return true;
                }
                for &x in &[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] {
                    if x < n && is_composite(x, n, s, d) {
                        return false;
                    }
                }
                true
            }
        }
    }
}