#545779 (Haskell) No.8030 ミラー・ラビン素数判定法のテスト

• 問題: No.8030 ミラー・ラビン素数判定法のテスト
• ユーザー: poapoa
• 提出日時: 2020-09-01 22:20:20
• 言語: Haskell (9.8.2)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 5,853 bytes
• コンパイル時間: 290 ms
• コンパイル使用メモリ: 169,216 KB
• 最終ジャッジ日時: 2024-11-14 23:48:05
• 合計ジャッジ時間: 640 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

コンパイルメッセージ

Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default

Main.hs:9:28: warning: [GHC-53692] [-Wdeprecated-flags]
    -XTypeInType is deprecated: use -XDataKinds and -XPolyKinds instead
  |
9 | {-# LANGUAGE TypeFamilies, TypeInType, UnboxedTuples, ViewPatterns  #-}
  |                            ^^^^^^^^^^
[1 of 2] Compiling Main             ( Main.hs, Main.o )

Main.hs:44:1: error: [GHC-61948]
    Could not find module ‘Data.ByteString.Lazy.Builder’.
    Perhaps you meant
      Data.ByteString.Builder (from bytestring-0.12.1.0)
      Data.ByteString.Lazy.Char8 (from bytestring-0.12.1.0)
      Data.ByteString.Lazy.ReadInt
    Use -v to see a list of the files searched for.
   |
44 | import qualified Data.ByteString.Lazy.Builder  as BSLB
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Main.hs:48:1: error: [GHC-87110]
    Could not load module ‘Data.Graph’.
    It is a member of the hidden package ‘containers-0.6.8’.
    Use -v to see a list of the files searched for.
   |
48 | import qualified Data.Graph                    as Graph
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Main.hs:49:1: error: [GHC-87110]
    Could not load module ‘Data.IntMap’.
    It is a member of the hidden package ‘containers-0.6.8’.
    Use -v to see a list of the files searched for.
   |
49 | import           Data.IntMap                   (IntMap)
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Main.hs:50:1: error: [GHC-87110]
    Could not load module ‘Data.IntMap’.
    It is a member of the hidden package ‘containers-0.6.8’.
    Use -v to see a list of the files searched for.
   |
50 | import qualified Data.IntMap                   as IntMap
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Main.hs:51:1: error: [GHC-87110]
    Could not load module ‘Data.IntSet’.
    It is a member of the hidden package ‘containers-0.6.8’.
    Use -v to see a list of the files searc

ソースコード

{-# LANGUAGE DeriveFunctor                                          #-}
{-# LANGUAGE BangPatterns, BinaryLiterals, CPP, DerivingStrategies  #-}
{-# LANGUAGE DerivingVia, FlexibleContexts, FlexibleInstances       #-}
{-# LANGUAGE GeneralizedNewtypeDeriving, KindSignatures, LambdaCase #-}
{-# LANGUAGE MagicHash, MultiParamTypeClasses, MultiWayIf           #-}
{-# LANGUAGE NumericUnderscores, OverloadedStrings, PatternSynonyms #-}
{-# LANGUAGE RankNTypes, RecordWildCards, ScopedTypeVariables       #-}
{-# LANGUAGE StandaloneDeriving, TupleSections, TypeApplications    #-}
{-# LANGUAGE TypeFamilies, TypeInType, UnboxedTuples, ViewPatterns  #-}

{- base -}
import           Control.Applicative
import qualified Control.Arrow                 as Arrow
import           Control.Monad
import           Control.Monad.ST
import           Data.Bits
import           Data.Bool
import           Data.Complex
import qualified Data.Char                     as Char
import qualified Data.Foldable                 as Foldable
import           Data.Function
import qualified Data.List                     as List
import           Data.Maybe
import           Data.Monoid
import           Data.Ratio
import           Data.Ord
import           Data.Semigroup
import qualified Data.Word                     as Word
import           Foreign                       hiding (void)
import           GHC.Exts
import           Unsafe.Coerce
{- array -}
import qualified Data.Array.IO                 as ArrIO
import qualified Data.Array.MArray             as ArrMA
import qualified Data.Array.ST                 as ArrST
import qualified Data.Array.Storable           as ArrStore
import qualified Data.Array.Unboxed            as ArrU
{- bytestring -}
import qualified Data.ByteString               as BS
import qualified Data.ByteString.Builder       as BSB
import qualified Data.ByteString.Builder.Extra as BSBE
import qualified Data.ByteString.Char8         as BSC8
import qualified Data.ByteString.Lazy          as BSL
import qualified Data.ByteString.Lazy.Builder  as BSLB
import qualified Data.ByteString.Lazy.Char8    as BSLC8
import qualified Data.ByteString.Unsafe        as BSU
{- containers -}
import qualified Data.Graph                    as Graph
import           Data.IntMap                   (IntMap)
import qualified Data.IntMap                   as IntMap
import           Data.IntSet                   (IntSet)
import qualified Data.IntSet                   as IntSet
import qualified Data.Sequence                 as Seq
import qualified Data.Tree                     as Tree
{- integer-gmp -}
import           GHC.Integer.GMP.Internals
{- vector -}
import qualified Data.Vector                   as V
import qualified Data.Vector.Generic           as VG
import qualified Data.Vector.Generic.Mutable   as VGM
import qualified Data.Vector.Mutable           as VM
import qualified Data.Vector.Primitive         as VP
import qualified Data.Vector.Primitive.Mutable as VPM
import qualified Data.Vector.Unboxed           as VU
import qualified Data.Vector.Unboxed.Mutable   as VUM


main :: IO ()
main = do
  n  <- parse1
  xs <- parseN n
  VU.mapM_ (BSC8.putStr . solve) xs

solve :: Int -> BSC8.ByteString
solve n
  | millerRabin n = tupToBS (n, 1)
  | otherwise     = tupToBS (n, 0)
  where
    tupToBS (a, b) = BSC8.pack $ show a ++ " " ++ show b ++ "\n"

-- miller rabin
millerRabin :: Int -> Bool
millerRabin n
  |  n <= 1 = False
  |  n == 2
  || n == 3
  || n == 5
  || n == 7 = True
  |  even n = False
  |  otherwise = mrCheck $ fromIntegral n
powerMR :: Integer -> Integer -> Integer -> Integer
powerMR b e m = loop 1 (b `mod` m) e
  where
    loop res base pxe
      | pxe <= 0 = res
      | otherwise =
        let res'  = if pxe `mod` 2 == 1 then (res * base) `mod` m else res
            pxe'  = shift pxe (-1)
            base' = (base * base) `mod` m
        in loop res' base' pxe'
factoringPowers :: Integer -> (Integer, Integer)
factoringPowers n = loop (n - 1) 0
  where
    loop d s
      | even d    = loop (d `div` 2) (s + 1)
      | otherwise = (s, d)
mrCheck :: Integer -> Bool
mrCheck p
  | p < 2047                = loop [2]
  | p < 9080191             = loop [31,73]
  | p < 4759123141          = loop [2,7,61]
  | p < 1122004669633       = loop [2,13,23,1662803]
  | p < 2152302898747       = loop [2,3,5,7,11]
  | p < 341550071728321     = loop [2,3,5,7,11,13,17]
  | p < 3825123056546413051 = loop [2,3,5,7,11,13,17,19,23]
  | p < 9223372036854775808 = loop [2,325,9375,28178,450775,9780504,1795265022]
  | otherwise               = loop [ 2 .. min (p - 1) (floor $ 2 * (log p')^(2 :: Int)) ]
  where
    p' = fromIntegral p :: Double
    (s, d) = factoringPowers p
    loop [] = True
    loop (a:as)
      | (powerMR a d p) /= 1 && powLoop 0 = False
      | otherwise = loop as
      where
        powLoop r
          | r < s     = (powerMR a (2 ^ r * d) p) /= (p - 1)  && powLoop (r + 1)
          | otherwise = True

-- input
type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString)
parseInt :: Parser Int
parseInt = fmap (Arrow.second BSC8.tail) . BSC8.readInt
parseChar :: [Char] -> VU.Vector Char
parseChar = VU.fromList
parse1 :: IO Int
parse1 = readLn
parse2 :: IO (Int, Int)
parse2 = (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldrN 2 parseInt <$> BSC8.getLine
parse3 :: IO (Int, Int, Int)
parse3 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldrN 3 parseInt <$> BSC8.getLine
parse4 :: IO (Int, Int, Int, Int)
parse4 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2, vec VU.! 3)) . VU.unfoldrN 4 parseInt <$> BSC8.getLine
parseM :: Int -> IO (VU.Vector Int)
parseM m = VU.unfoldrN m parseInt <$> BSC8.getLine
parseN :: Int -> IO (VU.Vector Int)
parseN n = VU.replicateM n parse1
parseNM :: Int -> Int -> IO (V.Vector (VU.Vector Int))
parseNM n m = V.replicateM n $ VU.unfoldrN m parseInt <$> BSC8.getLine