結果
問題 | No.3030 ミラー・ラビン素数判定法のテスト |
ユーザー | かりあげクン |
提出日時 | 2020-08-27 01:29:18 |
言語 | Haskell (9.8.2) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,013 bytes |
コンパイル時間 | 1,965 ms |
コンパイル使用メモリ | 204,544 KB |
実行使用メモリ | 8,192 KB |
最終ジャッジ日時 | 2024-04-29 14:12:08 |
合計ジャッジ時間 | 7,339 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | WA | - |
testcase_05 | AC | 871 ms
8,064 KB |
testcase_06 | AC | 436 ms
8,192 KB |
testcase_07 | AC | 440 ms
8,064 KB |
testcase_08 | AC | 438 ms
7,936 KB |
testcase_09 | AC | 1,520 ms
7,936 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 < 4759123141 = loop [2,7,61] | 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 p' = fromIntegral p :: Double (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