結果
問題 | No.3030 ミラー・ラビン素数判定法のテスト |
ユーザー | かりあげクン |
提出日時 | 2020-09-12 11:04:03 |
言語 | Haskell (9.8.2) |
結果 |
AC
|
実行時間 | 223 ms / 9,973 ms |
コード長 | 1,861 bytes |
コンパイル時間 | 1,178 ms |
コンパイル使用メモリ | 201,480 KB |
実行使用メモリ | 13,028 KB |
最終ジャッジ日時 | 2023-08-10 16:22:32 |
合計ジャッジ時間 | 2,744 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
7,748 KB |
testcase_01 | AC | 3 ms
7,680 KB |
testcase_02 | AC | 3 ms
8,012 KB |
testcase_03 | AC | 3 ms
8,204 KB |
testcase_04 | AC | 152 ms
12,868 KB |
testcase_05 | AC | 152 ms
13,028 KB |
testcase_06 | AC | 102 ms
12,880 KB |
testcase_07 | AC | 102 ms
12,876 KB |
testcase_08 | AC | 102 ms
12,896 KB |
testcase_09 | AC | 223 ms
12,916 KB |
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.6.1/environments/default [1 of 2] Compiling Main ( Main.hs, Main.o ) Main.hs:14:25: warning: [GHC-68441] [-Wdeprecations] In the use of ‘powModInteger’ (imported from GHC.Integer.GMP.Internals): Deprecated: "Use integerPowMod# instead" | 14 | powModInt a n mo = fI $ powModInteger (fi a) (fi n) (fi mo) | ^^^^^^^^^^^^^ [2 of 2] Linking a.out
ソースコード
import qualified Control.Arrow as Arrow import Data.Bits (Bits (unsafeShiftL, unsafeShiftR), FiniteBits (countTrailingZeros)) import Data.Bool (bool) import qualified Data.ByteString.Char8 as BSC8 import qualified Data.Vector.Unboxed as VU import GHC.Integer.GMP.Internals (powModInteger) fi :: Int -> Integer fi = fromIntegral fI :: Integer -> Int fI = fromInteger powModInt :: Int -> Int -> Int -> Int powModInt a n mo = fI $ powModInteger (fi a) (fi n) (fi mo) millerRabin :: Int -> Bool millerRabin n | n <= 3 = n == 2 || n == 3 | even n = False | otherwise = mrCheck n mrCheck :: Int -> Bool mrCheck n | n < 2047 = loop [2] | n < 9080191 = loop [31,73] | n < 4759123141 = loop [2,7,61] | n < 1122004669633 = loop [2,13,23,1662803] | n < 2152302898747 = loop [2,3,5,7,11] | n < 341550071728321 = loop [2,3,5,7,11,13,17] | otherwise = loop [2,325,9375,28178,450775,9780504,1795265022] where m = n - 1 s = countTrailingZeros m d = m `unsafeShiftR` s loop [] = True loop (a:as) | (powModInt (a `mod` n) d n /= 1) && allok = False | otherwise = loop as where allok = all (\r -> (powModInt a ((1 `unsafeShiftL` r) * d) n) /= m) [0..(s - 1)] type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString) parseInt :: Parser Int parseInt = fmap (Arrow.second BSC8.tail) . BSC8.readInt parse1 :: IO Int parse1 = readLn parseN :: Int -> IO (VU.Vector Int) parseN n = VU.replicateM n parse1 main :: IO () main = do n <- parse1 xs <- parseN n VU.mapM_ (BSC8.putStrLn . solve) xs solve :: Int -> BSC8.ByteString solve n = BSC8.pack $ bool (show n ++ " 0") (show n ++ " 1") (millerRabin n)