{-# OPTIONS_GHC -O2 #-} {-# LANGUAGE BangPatterns #-} {-# LANGUAGE Rank2Types #-} {-# LANGUAGE TupleSections #-} {-# LANGUAGE MagicHash #-} import qualified Control.Arrow as Arrow import qualified Control.Monad as Monad import qualified Data.Bool as Bool import qualified Data.Bits as Bits import qualified Data.ByteString.Char8 as BSC8 import qualified Data.Foldable as Foldable import qualified Data.List as List import qualified Data.Vector as V import qualified Data.Vector.Unboxed as VU import qualified Data.Vector.Unboxed.Mutable as VUM import qualified Data.Word as Word import Unsafe.Coerce ----------- -- 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 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 main :: IO () main = do n <- parse1 Monad.forM_ [0..n-1] $ \_ -> do parse1 >>= putStrLn . (\x -> show x ++ " " ++ Bool.bool "0" "1" (millerRabin x)) millerRabin :: Int -> Bool millerRabin n | n <= 1 = False | n == 2 || n == 3 || n == 5 || n == 7 = True | even n = False | otherwise = mrCheck $ fromIntegral n powMod :: Integer -> Integer -> Integer -> Integer powMod 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' = Bits.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] | otherwise = loop [2,325,9375,28178,450775,9780504,1795265022] where (s, d) = factoringPowers p loop [] = True loop (a:as) | (powMod a d p) /= 1 && powLoop 0 = False | otherwise = loop as where powLoop r | r < s = (powMod a (2 ^ r * d) p) /= (p - 1) && powLoop (r + 1) | otherwise = True