結果
問題 | No.3030 ミラー・ラビン素数判定法のテスト |
ユーザー | かりあげクン |
提出日時 | 2020-10-02 17:59:48 |
言語 | Haskell (9.6.2) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,039 bytes |
コンパイル時間 | 1,126 ms |
コンパイル使用メモリ | 206,684 KB |
実行使用メモリ | 12,092 KB |
最終ジャッジ日時 | 2023-08-11 23:11:19 |
合計ジャッジ時間 | 2,837 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
コンパイルメッセージ
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:75:34: warning: [GHC-68441] [-Wdeprecations] In the use of ‘powModInteger’ (imported from GHC.Integer.GMP.Internals): Deprecated: "Use integerPowMod# instead" | 75 | 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 qualified System.IO as SysIO 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 ------------------------------------------------------------------------------- main :: IO () main = do n <- readLn :: IO Int ps <- VU.map isPrime <$> parseN n BSB.hPutBuilder SysIO.stdout . VU.foldr ((<>) . bool (BSB.string8 "0\n") (BSB.string8 "1\n")) mempty $ ps ------------------------------------------------------------------------------- isPrime :: Int -> Bool isPrime n | n <= 3 = n == 2 || n == 3 | even n = False | 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 = m .>>. s check3 :: Int -> Bool check3 a = powModInt a d n /= 1 {-# INLINE check3 #-} check4 :: Int -> Int -> Bool check4 a i = (powModInt a (d * (1 .<<. i)) n) /= 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 #-}