結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー zeronosu77108zeronosu77108
提出日時 2022-03-23 14:47:26
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 398 ms / 9,973 ms
コード長 2,536 bytes
コンパイル時間 15,670 ms
コンパイル使用メモリ 378,452 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-16 23:46:57
合計ジャッジ時間 15,779 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 1 ms
5,248 KB
testcase_04 AC 215 ms
5,248 KB
testcase_05 AC 202 ms
5,248 KB
testcase_06 AC 64 ms
5,248 KB
testcase_07 AC 63 ms
5,248 KB
testcase_08 AC 64 ms
5,248 KB
testcase_09 AC 398 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

fn main() {
    let n : usize = input();
    for _ in 0..n {
        let x : usize = input();
        println!("{} {}", x, if miller_rabin(x as u128) {1} else {0});
    }
}

type MT = u128; fn miller_rabin(n : MT) -> bool { const P: [MT; 12] = [2,3,5,7,11,13,17,19,23,29,31,37]; let pow = |mut x:MT, mut n:MT, m:MT| { let mut res = 1; x %= m; while n != 0 { if n%2==1 { res *= x; res %= m; } x *= x; x %= m; n /= 2; } res }; if P.contains(&n) { return true; } if n <= 1 || n % 2 == 0 { return false; } let mut d = n - 1; while d % 2 == 0 { d /= 2; } for &p in P.iter() { let mut t = d; let mut y = pow(p, t, n); while t!=n-1 && y!=1 && y!=n-1 { y *= y; y %= n; t *= 2; } if y!=n-1 && t%2==0 { return false; } } true }#[allow(dead_code)] fn input<T: std::str::FromStr>() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } #[allow(dead_code)] fn input_t<T: std::str::FromStr, U: std::str::FromStr>() -> (T, U) { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); let s = s.trim().split_whitespace().collect::<Vec<&str>>(); (s[0].parse().ok().unwrap(), s[1].parse().ok().unwrap()) } #[allow(dead_code)] fn input_t3<T1: std::str::FromStr, T2: std::str::FromStr, T3: std::str::FromStr>() -> (T1, T2, T3) { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); let s = s.trim().split_whitespace().collect::<Vec<&str>>(); (s[0].parse().ok().unwrap(), s[1].parse().ok().unwrap(), s[2].parse().ok().unwrap()) } #[allow(dead_code)] fn input_t4<T1: std::str::FromStr, T2: std::str::FromStr, T3: std::str::FromStr, T4: std::str::FromStr>() -> (T1, T2, T3, T4) { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); let s = s.trim().split_whitespace().collect::<Vec<&str>>(); (s[0].parse().ok().unwrap(), s[1].parse().ok().unwrap(), s[2].parse().ok().unwrap(), s[3].parse().ok().unwrap()) } #[allow(dead_code)] fn input_t5<T1: std::str::FromStr, T2: std::str::FromStr, T3: std::str::FromStr, T4: std::str::FromStr, T5: std::str::FromStr>() -> (T1, T2, T3, T4, T5) { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); let s = s.trim().split_whitespace().collect::<Vec<&str>>(); (s[0].parse().ok().unwrap(), s[1].parse().ok().unwrap(), s[2].parse().ok().unwrap(), s[3].parse().ok().unwrap(), s[4].parse().ok().unwrap()) } #[allow(dead_code)] fn input_vec<T: std::str::FromStr>() -> Vec<T> { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().split_whitespace().map(|s| s.parse().ok().unwrap()).collect() }
0