結果
問題 | No.3030 ミラー・ラビン素数判定法のテスト |
ユーザー | かりあげクン |
提出日時 | 2020-09-24 18:39:45 |
言語 | Haskell (9.6.2) |
結果 |
AC
|
実行時間 | 222 ms / 9,973 ms |
コード長 | 3,155 bytes |
コンパイル時間 | 1,546 ms |
コンパイル使用メモリ | 186,868 KB |
実行使用メモリ | 13,028 KB |
最終ジャッジ日時 | 2023-08-10 16:24:50 |
合計ジャッジ時間 | 2,897 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
7,640 KB |
testcase_01 | AC | 3 ms
7,620 KB |
testcase_02 | AC | 3 ms
7,920 KB |
testcase_03 | AC | 3 ms
8,156 KB |
testcase_04 | AC | 142 ms
12,996 KB |
testcase_05 | AC | 142 ms
13,028 KB |
testcase_06 | AC | 102 ms
12,856 KB |
testcase_07 | AC | 102 ms
12,780 KB |
testcase_08 | AC | 103 ms
12,892 KB |
testcase_09 | AC | 222 ms
12,856 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:58:34: warning: [GHC-68441] [-Wdeprecations] In the use of ‘powModInteger’ (imported from GHC.Integer.GMP.Internals): Deprecated: "Use integerPowMod# instead" | 58 | powModInt a n mo = fromInteger $ GMP.powModInteger (fromIntegral a) (fromIntegral n) (fromIntegral mo) | ^^^^^^^^^^^^^^^^^ [2 of 2] Linking a.out
ソースコード
{-# LANGUAGE BangPatterns #-} 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.List as List import qualified Data.Vector.Unboxed as VU import qualified Data.Vector.Fusion.Stream.Monadic as MS import qualified GHC.Integer.GMP.Internals as GMP ------------------------------------------------------------------------------- main :: IO () main = do n <- parse1 xs <- parseN n rep n (\i -> BSC8.putStrLn $ solve $ xs VU.! i) solve :: Int -> BSC8.ByteString solve n = BSC8.pack $ bool (show n ++ " 0") (show n ++ " 1") (isPrime n) ------------------------------------------------------------------------------- isPrime :: Int -> Bool isPrime k | k <= 3 = k == 2 || k == 3 | even k = False | otherwise = millerRabin k where millerRabin :: Int -> Bool millerRabin n | n < 2047 = loop [2] | n < 1373653 = loop [2,3] | n < 9080191 = loop [31,73] | n < 25326001 = loop [2,3,5] | n < 4759123141 = loop [2,7,61] | n < 1122004669633 = loop [2,13,23,1662803] | n < 2152302898747 = loop [2,3,5,7,11] | n < 3474749660383 = loop [2,3,5,7,11,13] | 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 = unsafeShiftR m s check1 :: Int -> Bool check1 a = powModInt a d n /= 1 {-# INLINE check1 #-} check2 :: Int -> Int -> Bool check2 a i = (powModInt a (d * (unsafeShiftL 1 i)) n) /= m {-# INLINE check2 #-} loop [] = True loop (a:as) | check1 a && loop2 a [0..(s-1)] = False | otherwise = loop as where loop2 :: Int -> [Int] -> Bool loop2 _ [] = True loop2 t_ (r:rs) = check2 t_ r && loop2 t_ rs powModInt :: Int -> Int -> Int -> Int powModInt a n mo = fromInteger $ GMP.powModInteger (fromIntegral a) (fromIntegral n) (fromIntegral mo) {-# INLINE powModInt #-} ------------------------------------------------------------------------------- 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 ------------------------------------------------------------------------------- rep :: (Monad m) => Int -> (Int -> m ()) -> m () rep n = flip MS.mapM_ (stream 0 n) {-# INLINE rep #-} stream :: (Monad m) => Int -> Int -> MS.Stream m Int stream !l !r = MS.Stream step l where step x | x < r = return $ MS.Yield x (x + 1) | otherwise = return MS.Done {-# INLINE [0] step #-} {-# INLINE [1] stream #-}