結果
問題 | No.3030 ミラー・ラビン素数判定法のテスト |
ユーザー | siman |
提出日時 | 2020-01-14 18:38:00 |
言語 | Ruby (3.3.0) |
結果 |
AC
|
実行時間 | 3,260 ms / 9,973 ms |
コード長 | 852 bytes |
コンパイル時間 | 526 ms |
コンパイル使用メモリ | 11,480 KB |
実行使用メモリ | 20,900 KB |
最終ジャッジ日時 | 2023-08-10 16:13:34 |
合計ジャッジ時間 | 10,321 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 110 ms
20,360 KB |
testcase_01 | AC | 107 ms
20,420 KB |
testcase_02 | AC | 106 ms
20,080 KB |
testcase_03 | AC | 107 ms
20,076 KB |
testcase_04 | AC | 1,680 ms
20,748 KB |
testcase_05 | AC | 1,815 ms
20,708 KB |
testcase_06 | AC | 755 ms
20,636 KB |
testcase_07 | AC | 753 ms
20,900 KB |
testcase_08 | AC | 760 ms
20,880 KB |
testcase_09 | AC | 3,260 ms
20,648 KB |
コンパイルメッセージ
Syntax OK
ソースコード
require 'openssl' def modular_exponentiation(base, n, mod) res = 1 while n > 0 if n[0] == 1 res = (res * base) % mod end base = (base ** 2) % mod n >>= 1 end res end def witness(a, n) v = n - 1 t = 0 while v % 2 == 0 t += 1 v /= 2 end u = n / (2 ** t) x = modular_exponentiation(a, u, n) t.times do bx = x x = (x ** 2) % n if x == 1 && bx != 1 && bx != n - 1 return true end end return true if x != 1 false end def miller_rabin(n, s = 10) return false if n <= 1 return true if n == 2 return false if n.even? s.times do a = rand(n - 1) + 1 return false if witness(a, n) end true end N = gets.to_i N.times do x = gets.to_i bn = OpenSSL::BN.new(x) if bn.prime? puts [x, 1].join(' ') else puts [x, 0].join(' ') end end