結果
問題 | No.3030 ミラー・ラビン素数判定法のテスト |
ユーザー | かりあげクン |
提出日時 | 2020-10-02 18:13:39 |
言語 | Haskell (9.6.2) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,189 bytes |
コンパイル時間 | 1,401 ms |
コンパイル使用メモリ | 203,700 KB |
実行使用メモリ | 12,192 KB |
最終ジャッジ日時 | 2023-08-11 23:11:37 |
合計ジャッジ時間 | 2,863 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:78:34: warning: [GHC-68441] [-Wdeprecations] In the use of ‘powModInteger’ (imported from GHC.Integer.GMP.Internals): Deprecated: "Use integerPowMod# instead" | 78 | 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 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 | 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 #-}