結果
問題 | No.8030 ミラー・ラビン素数判定法のテスト |
ユーザー | こまる |
提出日時 | 2020-10-07 12:45:26 |
言語 | Haskell (9.8.2) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,688 bytes |
コンパイル時間 | 465 ms |
コンパイル使用メモリ | 152,064 KB |
最終ジャッジ日時 | 2024-11-15 05:00:58 |
合計ジャッジ時間 | 1,242 ms |
ジャッジサーバーID (参考情報) |
judge2 / 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:13: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. | 13 | import qualified GHC.Integer.GMP.Internals as GMP | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ソースコード
{-# LANGUAGE BangPatterns #-} {-# LANGUAGE OverloadedStrings #-} import Control.Monad.State import Data.Bits import Data.Bool import qualified System.IO as SysIO import qualified Data.ByteString.Char8 as BSC8 import qualified Data.ByteString.Lazy.Char8 as BSLC8 import qualified Data.ByteString.Builder as BSB import qualified Data.Vector.Generic as VG import qualified Data.Vector.Unboxed as VU import qualified GHC.Integer.GMP.Internals as GMP infixl 8 .<<., .>>. infixl 6 .^. (.<<.) :: Bits b => b -> Int -> b (.<<.) = unsafeShiftL {-# INLINE (.<<.) #-} (.>>.) :: Bits b => b -> Int -> b (.>>.) = unsafeShiftR {-# INLINE (.>>.) #-} (.^.) :: Bits b => b -> b -> b (.^.) = xor {-# INLINE (.^.) #-} fi :: Int -> Integer fi = fromIntegral {-# INLINE fi #-} fI :: Integer -> Int fI = fromInteger {-# INLINE fI #-} ctz :: FiniteBits fb => fb -> Int ctz = countTrailingZeros {-# INLINE ctz #-} powModInt :: Int -> Int -> Int -> Int powModInt !a !n !mo = fI $ GMP.powModInteger (fi a) (fi n) (fi mo) {-# INLINE powModInt #-} millerRabin :: Int -> Bool millerRabin 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 = ctz m !d = m .>>. s loop :: [Int] -> Bool loop [] = True loop (a:as) | powModInt a d n /= 1 && allok = False | otherwise = loop as where allok = all (\r -> (powModInt a ((1 .<<. r) * d) n) /= m) [0..(s - 1)] 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 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 SysIO.stdout {-# INLINE putBuilder #-} rInt :: StateT BSLC8.ByteString Maybe Int rInt = StateT $ BSLC8.readInt . BSLC8.dropWhile (<'!') {-# INLINE rInt #-}