結果
問題 | No.3030 ミラー・ラビン素数判定法のテスト |
ユーザー | かりあげクン |
提出日時 | 2020-10-02 18:35:08 |
言語 | Haskell (9.8.2) |
結果 |
AC
|
実行時間 | 203 ms / 9,973 ms |
コード長 | 3,230 bytes |
コンパイル時間 | 1,466 ms |
コンパイル使用メモリ | 197,460 KB |
実行使用メモリ | 12,016 KB |
最終ジャッジ日時 | 2023-08-10 16:25:29 |
合計ジャッジ時間 | 2,784 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
7,772 KB |
testcase_01 | AC | 2 ms
7,812 KB |
testcase_02 | AC | 3 ms
7,972 KB |
testcase_03 | AC | 3 ms
8,200 KB |
testcase_04 | AC | 142 ms
11,976 KB |
testcase_05 | AC | 143 ms
11,920 KB |
testcase_06 | AC | 93 ms
12,016 KB |
testcase_07 | AC | 92 ms
11,896 KB |
testcase_08 | AC | 92 ms
11,904 KB |
testcase_09 | AC | 203 ms
11,900 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:82:34: warning: [GHC-68441] [-Wdeprecations] In the use of ‘powModInteger’ (imported from GHC.Integer.GMP.Internals): Deprecated: "Use integerPowMod# instead" | 82 | powModInt a n mo = fromInteger $ GMP.powModInteger (fromIntegral a) (fromIntegral n) (fromIntegral mo) | ^^^^^^^^^^^^^^^^^ [2 of 2] Linking a.out
ソースコード
{-# LANGUAGE BangPatterns #-} {-# LANGUAGE OverloadedStrings #-} import qualified Control.Arrow as Arrow import Data.Bits (Bits (unsafeShiftL, unsafeShiftR), FiniteBits (countTrailingZeros)) import Data.Bool (bool) import qualified Data.ByteString.Builder as BSB import qualified Data.ByteString.Char8 as BSC8 import qualified Data.List as List import qualified Data.Vector.Fusion.Stream.Monadic as MS import qualified Data.Vector.Unboxed as VU import qualified GHC.Integer.GMP.Internals as GMP import qualified System.IO as SysIO ------------------------------------------------------------------------------- main :: IO () main = do n <- readLn :: IO Int rep n $ \_ -> do p <- readLn :: IO Int BSB.hPutBuilder SysIO.stdout $ solve p solve :: Int -> BSB.Builder solve n = BSB.string8 $! show n <> (bool " 0\n" " 1\n" (isPrime n)) ------------------------------------------------------------------------------- isPrime :: Int -> Bool isPrime n | n <= 3 = n == 2 || n == 3 | even n = False | otherwise = mr n where mr k | k < 2047 = loop [2] | k < 1373653 = loop [2,3] | k < 9080191 = loop [31,73] | k < 25326001 = loop [2,3,5] | k < 4759123141 = loop [2,7,61] | k < 1122004669633 = loop [2,13,23,1662803] | k < 2152302898747 = loop [2,3,5,7,11] | k < 3474749660383 = loop [2,3,5,7,11,13] | k < 341550071728321 = loop [2,3,5,7,11,13,17] | otherwise = loop [2,325,9375,28178,450775,9780504,1795265022] where !m = k - 1 !s = countTrailingZeros m !d = m .>>. s check3 :: Int -> Bool check3 a = powModInt a d k /= 1 {-# INLINE check3 #-} check4 :: Int -> Int -> Bool check4 a i = (powModInt a (d * (1 .<<. i)) k) /= m {-# INLINE check4 #-} loop [] = True loop (a:as) | check3 a && allok = False | otherwise = loop as where allok = all (check4 a) [0..(s - 1)] ------------------------------------------------------------------------------- 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 #-} infixl 8 .>>., .<<. (.>>.) :: Bits i => i -> Int -> i (.>>.) = unsafeShiftR {-# INLINE (.>>.) #-} (.<<.) :: Bits i => i -> Int -> i (.<<.) = unsafeShiftL {-# INLINE (.<<.) #-} powModInt :: Int -> Int -> Int -> Int powModInt a n mo = fromInteger $ GMP.powModInteger (fromIntegral a) (fromIntegral n) (fromIntegral mo) {-# INLINE powModInt #-} parse1 :: IO Int parse1 = readLn {-# INLINE parse1 #-} parseN :: Int -> IO (VU.Vector Int) parseN n = VU.replicateM n parse1 {-# INLINE parseN #-}