結果
問題 | No.8030 ミラー・ラビン素数判定法のテスト |
ユーザー | satonakatakumi |
提出日時 | 2021-08-15 13:10:00 |
言語 | Haskell (9.8.2) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 6,436 bytes |
コンパイル時間 | 721 ms |
コンパイル使用メモリ | 156,288 KB |
最終ジャッジ日時 | 2024-11-16 23:40:06 |
合計ジャッジ時間 | 1,074 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、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:20: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. | 20 | import qualified GHC.Integer.GMP.Internals as GMP | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ソースコード
{-# LANGUAGE BangPatterns #-} {-# LANGUAGE DefaultSignatures #-} {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE OverloadedStrings #-} {-# LANGUAGE UndecidableInstances #-} import Control.Monad import Control.Monad.ST import Control.Monad.State import Data.Bits import Data.Bool import Data.Char import Data.Coerce import Data.Int import Data.STRef.Strict import Data.Word import System.IO import qualified Data.ByteString as BS import qualified Data.ByteString.Builder as BSB import qualified Data.ByteString.Char8 as BSC8 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 import qualified Data.Vector.Unboxed.Mutable as VUM main :: IO () main = do n <- readLn :: IO Int vec <- VU.unfoldrN n (runParser int) <$> BSC8.getContents putBuilder $ v2BLinesWith (\b -> BSB.byteString $ BSC8.pack $ show b ++ bool " 0" " 1" (millerRabin b)) vec 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 < 4759123141 = loop [2,7,61] | otherwise = loop [2,325,9375,28178,450775,9780504,1795265022] where !m = n - 1 !s = countTrailingZeros m !d = m `unsafeShiftR`s loop :: [Int] -> Bool loop pro = runST $ do ret <- newSTRef True forM_ pro $ \a -> do c <- readSTRef ret when (c && a < n) $ do let check1 = powModInt a d n /= 1 check2 = all (\r -> powModInt a ((1 `unsafeShiftL` r) * d) n /= m) ([0 .. (s - 1)] :: [Int]) when (check1 && check2) $ writeSTRef ret False readSTRef ret powModInt :: Int -> Int -> Int -> Int powModInt a n mo = fromInteger $ GMP.powModInteger (fromIntegral a) (fromIntegral n) (fromIntegral mo) {-# INLINE powModInt #-} type Parser a = StateT BSC8.ByteString Maybe a runParser :: Parser a -> BSC8.ByteString -> Maybe (a, BSC8.ByteString) runParser = runStateT {-# INLINE runParser #-} int :: Parser Int int = coerce $ BSC8.readInt . BSC8.dropWhile isSpace {-# INLINE int #-} class ShowAsBuilder a where showAsBuilder :: a -> BSB.Builder default showAsBuilder :: (Show a) => a -> BSB.Builder showAsBuilder = BSB.string8 . show instance ShowAsBuilder Int where showAsBuilder = BSB.intDec {-# INLINE showAsBuilder #-} instance ShowAsBuilder Int8 where showAsBuilder = BSB.int8Dec {-# INLINE showAsBuilder #-} instance ShowAsBuilder Int16 where showAsBuilder = BSB.int16Dec {-# INLINE showAsBuilder #-} instance ShowAsBuilder Int32 where showAsBuilder = BSB.int32Dec {-# INLINE showAsBuilder #-} instance ShowAsBuilder Int64 where showAsBuilder = BSB.int64Dec {-# INLINE showAsBuilder #-} instance ShowAsBuilder Word8 where showAsBuilder = BSB.word8Dec {-# INLINE showAsBuilder #-} instance ShowAsBuilder Word16 where showAsBuilder = BSB.word16Dec {-# INLINE showAsBuilder #-} instance ShowAsBuilder Word32 where showAsBuilder = BSB.word32Dec {-# INLINE showAsBuilder #-} instance ShowAsBuilder Word64 where showAsBuilder = BSB.word64Dec {-# INLINE showAsBuilder #-} instance ShowAsBuilder Integer where showAsBuilder = BSB.integerDec {-# INLINE showAsBuilder #-} instance ShowAsBuilder Float where showAsBuilder = BSB.floatDec {-# INLINE showAsBuilder #-} instance ShowAsBuilder Double where showAsBuilder = BSB.doubleDec {-# INLINE showAsBuilder #-} instance (ShowAsBuilder a, VG.Vector v a) => ShowAsBuilder (v a) where showAsBuilder = v2BSpcSep putBuilder :: BSB.Builder -> IO () putBuilder = BSB.hPutBuilder stdout {-# INLINE putBuilder #-} printVecInLines :: (VG.Vector v a, ShowAsBuilder a) => v a -> IO () printVecInLines = putBuilder . v2BLines {-# INLINE printVecInLines #-} printVecInSpcSepLn :: (VG.Vector v a, ShowAsBuilder a) => v a -> IO () printVecInSpcSepLn = putBuilder . v2BSpcSepLn {-# INLINE printVecInSpcSepLn #-} v2BSpcSepLn :: (VG.Vector v a, ShowAsBuilder a) => v a -> BSB.Builder v2BSpcSepLn = v2BSpcSepLnWith showAsBuilder {-# INLINE v2BSpcSepLn #-} v2BSpcSep :: (VG.Vector v a, ShowAsBuilder a) => v a -> BSB.Builder v2BSpcSep = v2BSpcSepWith showAsBuilder {-# INLINE v2BSpcSep #-} v2BConcat:: (VG.Vector v a, ShowAsBuilder a) => v a -> BSB.Builder v2BConcat = v2BConcatWith showAsBuilder {-# INLINE v2BConcat #-} v2BLines:: (VG.Vector v a, ShowAsBuilder a) => v a -> BSB.Builder v2BLines = v2BLinesWith showAsBuilder {-# INLINE v2BLines #-} v2BSpcSepLnWith :: VG.Vector v a => (a -> BSB.Builder) -> v a -> BSB.Builder v2BSpcSepLnWith = v2BSpcSepPostfWith "\n" {-# INLINE v2BSpcSepLnWith #-} v2BSpcSepWith :: VG.Vector v a => (a -> BSB.Builder) -> v a -> BSB.Builder v2BSpcSepWith = v2BSpcSepPostfWith "" {-# INLINE v2BSpcSepWith #-} v2BConcatWith :: VG.Vector v a => (a -> BSB.Builder) -> v a -> BSB.Builder v2BConcatWith showFct = VG.foldr ((<>) . showFct) mempty {-# INLINE v2BConcatWith #-} v2BLinesWith :: VG.Vector v a => (a -> BSB.Builder) -> v a -> BSB.Builder v2BLinesWith showFct = VG.foldr (\a -> (showFct a <>) . (BSB.char7 '\n' <>)) mempty {-# INLINE v2BLinesWith #-} v2BSpcSepPostf :: (VG.Vector v a, ShowAsBuilder a) => BS.ByteString -> v a -> BSB.Builder v2BSpcSepPostf = (`v2BSpcSepPostfWith` showAsBuilder) {-# INLINE v2BSpcSepPostf #-} v2BSpcSepPostfWith :: VG.Vector v a => BS.ByteString -> (a -> BSB.Builder) -> v a -> BSB.Builder v2BSpcSepPostfWith = vecToBuilder "" " " {-# INLINE v2BSpcSepPostfWith #-} vecToBuilder :: VG.Vector v a => BS.ByteString -> BS.ByteString -> BS.ByteString -> (a -> BSB.Builder) -> v a -> BSB.Builder vecToBuilder !prefix !separator !postfix = vecToBuilder_ (BSB.byteString prefix) (BSB.byteString separator) (BSB.byteString postfix) {-# INLINE vecToBuilder #-} vecToBuilder_ :: VG.Vector v a => BSB.Builder -> BSB.Builder -> BSB.Builder -> (a -> BSB.Builder) -> v a -> BSB.Builder vecToBuilder_ !prefix !separator !postfix showFct vec = prefix <> VG.foldr (\a rest !prefx -> prefx <> (showFct a <> rest separator)) (const postfix) vec mempty {-# INLINE vecToBuilder_ #-}