結果
| 問題 |
No.8030 ミラー・ラビン素数判定法のテスト
|
| ユーザー |
 satonakatakumi
|
| 提出日時 | 2021-08-09 12:49:20 |
| 言語 | Haskell (9.10.1) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 7,301 bytes |
| コンパイル時間 | 896 ms |
| コンパイル使用メモリ | 152,192 KB |
| 最終ジャッジ日時 | 2024-11-16 23:40:05 |
| 合計ジャッジ時間 | 1,214 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、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:26: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.
|
26 | import qualified GHC.Integer.GMP.Internals as GMP
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ソースコード
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE DefaultSignatures #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE UndecidableInstances #-}
-- module Yukicoder.No3030 where
-- base
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
-- bytestring
import qualified Data.ByteString as BS
import qualified Data.ByteString.Builder as BSB
import qualified Data.ByteString.Char8 as BSC8
-- gmp-integer
import qualified GHC.Integer.GMP.Internals as GMP
-- vector
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
rep n $ \i -> do
let
x = vec VU.! i
p = millerRabin x
putBuilder $ BSB.intDec x <> bool " 0\n" " 1\n" p
-- miller rabin
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 = 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
-- utils
powModInt :: Int -> Int -> Int -> Int
powModInt a n mo = fromInteger $ GMP.powModInteger (fromIntegral a) (fromIntegral n) (fromIntegral mo)
{-# INLINE powModInt #-}
rep :: Monad m => Int -> (Int -> m ()) -> m ()
rep n = flip VFSM.mapM_ (stream 0 n)
{-# INLINE rep #-}
stream :: Monad m => Int -> Int -> VFSM.Stream m Int
stream !l !r = VFSM.Stream step l
where
step x
| x < r = return $ VFSM.Yield x (x + 1)
| otherwise = return VFSM.Done
{-# INLINE [0] step #-}
{-# INLINE [1] stream #-}
-- input
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 #-}
-- output
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_ #-}