結果
| 問題 | No.8030 ミラー・ラビン素数判定法のテスト |
| ユーザー |
 Haar
|
| 提出日時 | 2021-09-23 22:51:44 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 382 ms / 9,973 ms |
| コード長 | 5,116 bytes |
| コンパイル時間 | 13,711 ms |
| コンパイル使用メモリ | 379,212 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-11-16 23:40:32 |
| 合計ジャッジ時間 | 15,105 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 10 |
コンパイルメッセージ
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}}}}