結果
問題 | No.8030 ミラー・ラビン素数判定法のテスト |
ユーザー | こまる |
提出日時 | 2020-11-19 03:33:54 |
言語 | Haskell (9.8.2) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 6,188 bytes |
コンパイル時間 | 470 ms |
コンパイル使用メモリ | 152,320 KB |
最終ジャッジ日時 | 2024-11-15 05:02:02 |
合計ジャッジ時間 | 910 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default [1 of 2] Compiling Main ( Main.hs, Main.o ) Main.hs:15:1: error: [GHC-87110] Could not load module ‘GHC.Integer.GMP.Internals’. It is a member of the hidden package ‘integer-gmp-1.1’. Use -v to see a list of the files searched for. | 15 | import qualified GHC.Integer.GMP.Internals as GMP | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ソースコード
{-# LANGUAGE BangPatterns #-} {-# LANGUAGE OverloadedLists #-} import Control.Monad import Control.Monad.Cont import Control.Monad.ST import Control.Monad.State import Data.Bits import Data.Bool import Data.STRef.Strict import System.IO import qualified Data.ByteString.Builder as BSB import qualified Data.ByteString.Char8 as BSC8 import qualified Data.ByteString.Lazy.Char8 as BSLC8 import qualified GHC.Integer.GMP.Internals as GMP import qualified Data.Vector.Fusion.Stream.Monadic as VFSM import qualified Data.Vector.Generic as VG import qualified Data.Vector.Unboxed as VU main :: IO () main = do q <- readLn :: IO Int xs <- VU.unfoldrN q (runStateT rInt) <$> BSLC8.getContents putBuilder $ v2BLinesWith (\b -> BSB.byteString $ BSC8.pack $ show b ++ bool " 0" " 1" (millerRabin b)) xs millerRabin :: Int -> Bool millerRabin k | k <= 3 = k == 2 || k == 3 | k .&. 1 == 0 = 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 = ctz m !d = m .>>. s loop :: VU.Vector Int -> Bool loop vec = runST $ do ret <- newSTRef True withBreakST $ \break1 -> do VU.forM_ vec $ \a -> do let check1 = powModInt a d n /= 1 check2 = runST $ do res <- newSTRef True withBreakST $ \break2 -> rep s $ \r -> when (powModInt a ((1 .<<. r) * d) n == m) $ do lift $ writeSTRef res False break2 () readSTRef res when (check1 && check2) $ do lift $ writeSTRef ret False break1 () readSTRef ret powModInt :: Int -> Int -> Int -> Int powModInt a n mo = fI $ GMP.powModInteger (fi a) (fi n) (fi mo) {-# INLINE powModInt #-} recipModInt :: Int -> Int -> Int recipModInt a mo = fI $ GMP.recipModInteger (fi a) (fi mo) {-# INLINE recipModInt #-} fi :: Int -> Integer fi = fromIntegral {-# INLINE fi #-} fI :: Integer -> Int fI = fromInteger {-# INLINE fI #-} clz :: FiniteBits fb => fb -> Int clz = countLeadingZeros {-# INLINE clz #-} ctz :: FiniteBits fb => fb -> Int ctz = countTrailingZeros {-# INLINE ctz #-} infixl 8 .<<., .>>. (.<<.) :: Bits b => b -> Int -> b (.<<.) = unsafeShiftL {-# INLINE (.<<.) #-} (.>>.) :: Bits b => b -> Int -> b (.>>.) = unsafeShiftR {-# INLINE (.>>.) #-} rep :: Monad m => Int -> (Int -> m ()) -> m () rep n = flip VFSM.mapM_ (streamG 0 (n - 1) const 0 (+) 1) {-# INLINE rep #-} rep' :: Monad m => Int -> (Int -> m ()) -> m () rep' n = flip VFSM.mapM_ (streamG 0 n const 0 (+) 1) {-# INLINE rep' #-} rep1 :: Monad m => Int -> (Int -> m ()) -> m () rep1 n = flip VFSM.mapM_ (streamG 1 (n - 1) const 0 (+) 1) {-# INLINE rep1 #-} rep1' :: Monad m => Int -> (Int -> m ()) -> m () rep1' n = flip VFSM.mapM_ (streamG 1 n const 0 (+) 1) {-# INLINE rep1' #-} rev :: Monad m => Int -> (Int -> m ()) -> m () rev n = flip VFSM.mapM_ (streamRG (n - 1) 0 const 0 (-) 1) {-# INLINE rev #-} rev' :: Monad m => Int -> (Int -> m ()) -> m () rev' n = flip VFSM.mapM_ (streamRG n 0 const 0 (-) 1) {-# INLINE rev' #-} rev1 :: Monad m => Int -> (Int -> m ()) -> m () rev1 n = flip VFSM.mapM_ (streamRG (n - 1) 1 const 0 (-) 1) {-# INLINE rev1 #-} rev1' :: Monad m => Int -> (Int -> m ()) -> m () rev1' n = flip VFSM.mapM_ (streamRG n 1 const 0 (-) 1) {-# INLINE rev1' #-} range :: Monad m => Int -> Int -> (Int -> m ()) -> m () range l r = flip VFSM.mapM_ (streamG l r const 0 (+) 1) {-# INLINE range #-} rangeR :: Monad m => Int -> Int -> (Int -> m ()) -> m () rangeR r l = flip VFSM.mapM_ (streamRG r l const 0 (-) 1) {-# INLINE rangeR #-} forP :: Monad m => Int -> (Int -> m ()) -> m () forP p = flip VFSM.mapM_ (streamG 2 (p - 1) (^) 2 (+) 1) {-# INLINE forP #-} forG :: Monad m => Int -> Int -> (Int -> Int -> Int) -> Int -> (Int -> Int -> Int) -> Int -> (Int -> m ()) -> m () forG l r f p g d = flip VFSM.mapM_ (streamG l r f p g d) {-# INLINE forG #-} forRG :: Monad m => Int -> Int -> (Int -> Int -> Int) -> Int -> (Int -> Int -> Int) -> Int -> (Int -> m ()) -> m () forRG r l f p g d = flip VFSM.mapM_ (streamRG r l f p g d) {-# INLINE forRG #-} streamG :: Monad m => Int -> Int -> (Int -> Int -> Int) -> Int -> (Int -> Int -> Int) -> Int -> VFSM.Stream m Int streamG !l !r !f !p !g !d = VFSM.Stream step l where step x | f x p <= r = return $ VFSM.Yield x (g x d) | otherwise = return VFSM.Done {-# INLINE [0] step #-} {-# INLINE [1] streamG #-} streamRG :: Monad m => Int -> Int -> (Int -> Int -> Int) -> Int -> (Int -> Int -> Int) -> Int -> VFSM.Stream m Int streamRG !r !l !f !p !g !d = VFSM.Stream step r where step x | f x p >= l = return $ VFSM.Yield x (g x d) | otherwise = return VFSM.Done {-# INLINE [0] step #-} {-# INLINE [1] streamRG #-} withBreakIO :: ((r -> ContT r IO b) -> ContT r IO r) -> IO r withBreakIO = flip runContT pure . callCC {-# INLINE withBreakIO #-} withBreakST :: ((r -> ContT r (ST s) b) -> ContT r (ST s) r) -> (ST s) r withBreakST = flip runContT pure . callCC {-# INLINE withBreakST #-} v2BLinesWith :: VG.Vector v t => (t -> BSB.Builder) -> v t -> BSB.Builder v2BLinesWith showFct = VG.foldr (\ a -> (showFct a <>) . (BSB.char7 '\n' <>)) mempty {-# INLINE v2BLinesWith #-} putBuilder :: BSB.Builder -> IO () putBuilder = BSB.hPutBuilder stdout {-# INLINE putBuilder #-} rInt :: StateT BSLC8.ByteString Maybe Int rInt = StateT $ BSLC8.readInt . BSLC8.dropWhile (<'!') {-# INLINE rInt #-}