結果
問題 | No.3030 ミラー・ラビン素数判定法のテスト |
ユーザー | かりあげクン |
提出日時 | 2020-09-30 10:10:45 |
言語 | Haskell (9.6.2) |
結果 |
AC
|
実行時間 | 223 ms / 9,973 ms |
コード長 | 4,035 bytes |
コンパイル時間 | 931 ms |
コンパイル使用メモリ | 198,892 KB |
実行使用メモリ | 12,964 KB |
最終ジャッジ日時 | 2023-08-10 16:25:32 |
合計ジャッジ時間 | 2,714 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
7,856 KB |
testcase_01 | AC | 2 ms
7,672 KB |
testcase_02 | AC | 3 ms
8,024 KB |
testcase_03 | AC | 3 ms
8,284 KB |
testcase_04 | AC | 152 ms
12,888 KB |
testcase_05 | AC | 152 ms
12,852 KB |
testcase_06 | AC | 102 ms
12,740 KB |
testcase_07 | AC | 102 ms
12,960 KB |
testcase_08 | AC | 102 ms
12,808 KB |
testcase_09 | AC | 223 ms
12,964 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:42:20: warning: [GHC-68441] [-Wdeprecations] In the use of ‘powModInteger’ (imported from GHC.Integer.GMP.Internals): Deprecated: "Use integerPowMod# instead" | 42 | check1 a = GMP.powModInteger a d n /= 1 | ^^^^^^^^^^^^^^^^^ Main.hs:45:23: warning: [GHC-68441] [-Wdeprecations] In the use of ‘powModInteger’ (imported from GHC.Integer.GMP.Internals): Deprecated: "Use integerPowMod# instead" | 45 | check2 a i = (GMP.powModInteger a (d * (1 .<<. i)) n) /= m | ^^^^^^^^^^^^^^^^^ Main.hs:112:34: warning: [GHC-68441] [-Wdeprecations] In the use of ‘powModInteger’ (imported from GHC.Integer.GMP.Internals): Deprecated: "Use integerPowMod# instead" | 112 | 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.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 rep n $ \_ -> do x <- readLn :: IO Integer BSC8.putStrLn $ solve x solve :: Integer -> BSC8.ByteString solve n = BSC8.pack $ show n ++ (bool " 0" " 1" (isPrime n)) ------------------------------------------------------------------------------- isPrime :: Integer -> Bool isPrime k | k <= 3 = k == 2 || k == 3 | even k = False | otherwise = millerRabin k where millerRabin :: Integer -> Bool millerRabin n | n < 18446744073709551616 = millerRabinSmall (fromInteger n) | n < 318665857834031151167461 = loop [2,3,5,7,11,13,17,19,23,29,31,37] | otherwise = loop [2,3,5,7,11,13,17,19,23,29,31,37,41] where !m = n - 1 !s = cTZ m 0 !d = m .>>. s cTZ :: Integer -> Int -> Int cTZ !i !cnt | odd i = cnt | otherwise = cTZ (i .>>. 1) (cnt + 1) {-# INLINE cTZ #-} check1 :: Integer -> Bool check1 a = GMP.powModInteger a d n /= 1 {-# INLINE check1 #-} check2 :: Integer -> Int -> Bool check2 a i = (GMP.powModInteger a (d * (1 .<<. i)) n) /= m {-# INLINE check2 #-} loop [] = True loop (a:as) | check1 a && allok = False | otherwise = loop as where allok = all (check2 a) [0..(s - 1)] millerRabinSmall :: Int -> Bool millerRabinSmall k | k <= 3 = k == 2 || k == 3 | even k = False | otherwise = mr k where mr :: Int -> Bool mr 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 check3 :: Int -> Bool check3 a = powModInt a d n /= 1 {-# INLINE check3 #-} check4 :: Int -> Int -> Bool check4 a i = (powModInt a (d * (unsafeShiftL 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 #-}