結果
問題 | No.3030 ミラー・ラビン素数判定法のテスト |
ユーザー | かりあげクン |
提出日時 | 2020-08-27 01:44:59 |
言語 | Haskell (9.8.2) |
結果 |
AC
|
実行時間 | 1,376 ms / 9,973 ms |
コード長 | 3,162 bytes |
コンパイル時間 | 7,814 ms |
コンパイル使用メモリ | 203,008 KB |
実行使用メモリ | 8,064 KB |
最終ジャッジ日時 | 2024-11-16 23:27:59 |
合計ジャッジ時間 | 12,596 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 831 ms
7,936 KB |
testcase_05 | AC | 809 ms
8,064 KB |
testcase_06 | AC | 395 ms
8,064 KB |
testcase_07 | AC | 407 ms
8,064 KB |
testcase_08 | AC | 405 ms
7,936 KB |
testcase_09 | AC | 1,376 ms
8,064 KB |
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default [1 of 2] Compiling Main ( Main.hs, Main.o ) [2 of 2] Linking a.out
ソースコード
{-# OPTIONS_GHC -O2 #-} {-# LANGUAGE BangPatterns #-} {-# LANGUAGE Rank2Types #-} {-# LANGUAGE TupleSections #-} {-# LANGUAGE MagicHash #-} import qualified Control.Arrow as Arrow import qualified Control.Monad as Monad import qualified Data.Bool as Bool import qualified Data.Bits as Bits import qualified Data.ByteString.Char8 as BSC8 import qualified Data.Foldable as Foldable import qualified Data.List as List import qualified Data.Vector as V import qualified Data.Vector.Unboxed as VU import qualified Data.Vector.Unboxed.Mutable as VUM import qualified Data.Word as Word import Unsafe.Coerce ----------- -- input -- ----------- type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString) parseInt :: Parser Int parseInt = fmap (Arrow.second BSC8.tail) . BSC8.readInt parseChar :: [Char] -> VU.Vector Char parseChar = VU.fromList parse1 :: IO Int parse1 = readLn parse2 :: IO (Int, Int) parse2 = (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 parseInt <$> BSC8.getLine parse3 :: IO (Int, Int, Int) parse3 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldrN 3 parseInt <$> BSC8.getLine parseM :: Int -> IO (VU.Vector Int) parseM m = VU.unfoldrN m parseInt <$> BSC8.getLine parseN :: Int -> IO (VU.Vector Int) parseN n = VU.replicateM n parse1 parseNM :: Int -> Int -> IO (V.Vector (VU.Vector Int)) parseNM n m = V.replicateM n $ VU.unfoldrN m parseInt <$> BSC8.getLine main :: IO () main = do n <- parse1 Monad.forM_ [0..n-1] $ \_ -> do parse1 >>= putStrLn . (\x -> show x ++ " " ++ Bool.bool "0" "1" (millerRabin x)) millerRabin :: Int -> Bool millerRabin n | n <= 1 = False | n == 2 || n == 3 || n == 5 || n == 7 = True | even n = False | otherwise = mrCheck $ fromIntegral n powMod :: Integer -> Integer -> Integer -> Integer powMod b e m = loop 1 (b `mod` m) e where loop res base pxe | pxe <= 0 = res | otherwise = let res' = if pxe `mod` 2 == 1 then (res * base) `mod` m else res pxe' = Bits.shift pxe (-1) base' = (base * base) `mod` m in loop res' base' pxe' factoringPowers :: Integer -> (Integer, Integer) factoringPowers n = loop (n - 1) 0 where loop d s | even d = loop (d `div` 2) (s + 1) | otherwise = (s, d) mrCheck :: Integer -> Bool mrCheck p | p < 2047 = loop [2] | p < 9080191 = loop [31,73] | p < 4759123141 = loop [2,7,61] | p < 1122004669633 = loop [2,13,23,1662803] | p < 2152302898747 = loop [2,3,5,7,11] | p < 341550071728321 = loop [2,3,5,7,11,13,17] | p < 3825123056546413051 = loop [2,3,5,7,11,13,17,19,23] | otherwise = loop [2,325,9375,28178,450775,9780504,1795265022] where (s, d) = factoringPowers p loop [] = True loop (a:as) | (powMod a d p) /= 1 && powLoop 0 = False | otherwise = loop as where powLoop r | r < s = (powMod a (2 ^ r * d) p) /= (p - 1) && powLoop (r + 1) | otherwise = True