#557774 (Haskell) No.1140 EXPotentiaLLL!

• 問題: No.1140 EXPotentiaLLL!
• ユーザー: かりあげクン
• 提出日時: 2020-09-25 13:52:18
• 言語: Haskell (9.8.2)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 6,583 bytes
• コンパイル時間: 206 ms
• コンパイル使用メモリ: 169,096 KB
• 最終ジャッジ日時: 2024-04-27 03:30:18
• 合計ジャッジ時間: 2,825 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

コンパイルメッセージ

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:52: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.
   |
52 | import qualified GHC.Integer.GMP.Internals         as GMP
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Main.hs:53:1: error: [GHC-87110]
    Could not find module ‘GHC.Integer.Logarithms.Internals’.
    Use -v to see a list of the files searched for.
   |
53 | import qualified GHC.Integer.Logarithms.Internals  as Log
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

ソースコード

{-# LANGUAGE BangPatterns               #-}
{-# LANGUAGE CPP                        #-}
{-# LANGUAGE DerivingStrategies         #-}
{-# LANGUAGE FlexibleContexts           #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE MagicHash                  #-}
{-# LANGUAGE MultiParamTypeClasses      #-}
{-# LANGUAGE RankNTypes                 #-}
{-# LANGUAGE RecordWildCards            #-}
{-# LANGUAGE ScopedTypeVariables        #-}
{-# LANGUAGE TypeApplications           #-}
{-# LANGUAGE TypeFamilies               #-}
{-# LANGUAGE UnboxedTuples              #-}
{- base -}
import           Control.Arrow
import           Control.Monad
import           Control.Monad.ST
import           Data.Bits
import           Data.Bool
import           Data.Char
import           Data.Coerce
import           Data.Function
import           Data.Functor.Identity
import           Data.IORef
import           Data.Ix
import           Data.Monoid
import           Data.Ord
import           Data.Ratio
import           Data.Semigroup
import           Data.STRef
import           Data.Void
import           Data.Word
import           GHC.Exts
import           Unsafe.Coerce
{- array -}
import qualified Data.Array                        as Arr
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.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.Builder.Prim      as BSBP
import qualified Data.ByteString.Char8             as BSC8
import qualified Data.ByteString.Lazy              as BSL
import qualified Data.ByteString.Lazy.Char8        as BSLC8
import qualified Data.ByteString.Short             as BSS
import qualified Data.ByteString.Unsafe            as BSU
{- integer-gmp -}
import qualified GHC.Integer.GMP.Internals         as GMP
import qualified GHC.Integer.Logarithms.Internals  as Log
{- vector -}
import qualified Data.Vector                       as V
import qualified Data.Vector.Fusion.Stream.Monadic as VFSM
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.Storable              as VS
import qualified Data.Vector.Storable.Mutable      as VSM
import qualified Data.Vector.Unboxed               as VU
import qualified Data.Vector.Unboxed.Mutable       as VUM
-------------------------------------------------------------------------------
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 #-}

rep :: Monad m => Int -> (Int -> m ()) -> m ()
rep n = flip VFSM.mapM_ (stream 0 n)
{-# INLINE rep #-}

fi :: Int -> Integer
fi = fromIntegral
{-# INLINE fi #-}

fI :: Integer -> Int
fI = fromInteger
{-# INLINE fI #-}

powModInt :: Int -> Int -> Int -> Int
powModInt a b c = fI $ GMP.powModInteger (fi a) (fi b) (fi c)
{-# INLINE powModInt #-}

(.>>.) :: Bits i => i -> Int -> i
(.>>.) = unsafeShiftR
{-# INLINE (.>>.) #-}

(.<<.) :: Bits i => i -> Int -> i
(.<<.) = unsafeShiftL
{-# INLINE (.<<.) #-}
-------------------------------------------------------------------------------
type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString)
parseInt :: Parser Int
parseInt = fmap (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
parseANBN :: Int -> IO (VU.Vector Int, VU.Vector Int)
parseANBN n = do
  vectup <- VU.replicateM n $ (\vec -> (vec VU.! 0, vec VU.! 1)) . VU.unfoldr (BSC8.readInt . BSC8.dropWhile isSpace) <$> BSC8.getLine
  return $ VU.unzip vectup
parseANBNCN :: Int -> IO (VU.Vector Int, VU.Vector Int, VU.Vector Int)
parseANBNCN n = do
  vectup <- VU.replicateM n $ (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2)) . VU.unfoldr (BSC8.readInt . BSC8.dropWhile isSpace) <$> BSC8.getLine
  return $ VU.unzip3 vectup
-------------------------------------------------------------------------------
isPrime :: Int -> Bool
isPrime k
  | k <= 3 = k == 2 || k == 3
  | even k = 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 .>>. s
        check1 :: Int -> Bool
        check1 a = powModInt a d n /= 1
        {-# INLINE check1 #-}
        check2 :: Int -> Int -> Bool
        check2 a i = (powModInt a (d * (1 .<<. i)) n) /= m
        {-# INLINE check2 #-}
        loop [] = True
        loop (a:as)
          | check1 a && allok = False
          | otherwise = loop as
          where allok = all (check2 a) [0..(s - 1)]
-------------------------------------------------------------------------------
main :: IO ()
main = do
  query <- parse1
  rep query $ \_ -> do
    (a, p) <- parse2
    if isPrime p
      then do
        print $ bool 0 1 (gcd a p == 1)
      else print (-1)