Submit Info #28794

Problem Lang User Status Time Memory
Tetration Mod haskell Itomi AC 1478 ms 1.92 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.80 MiB
example_01 AC 1 ms 0.77 MiB
max_00 AC 700 ms 1.86 MiB
max_01 AC 697 ms 1.87 MiB
max_02 AC 698 ms 1.92 MiB
max_1000000000_00 AC 1050 ms 1.81 MiB
max_1000000000_01 AC 1050 ms 1.92 MiB
max_1000000000_02 AC 1050 ms 1.81 MiB
max_998244353_00 AC 1476 ms 1.82 MiB
max_998244353_01 AC 1476 ms 1.80 MiB
max_998244353_02 AC 1478 ms 1.92 MiB
random_00 AC 485 ms 1.86 MiB
random_01 AC 141 ms 1.80 MiB
random_02 AC 65 ms 1.57 MiB
random_03 AC 146 ms 1.84 MiB
random_04 AC 388 ms 1.80 MiB
small_00 AC 3 ms 1.76 MiB

{-# LANGUAGE BangPatterns #-} import qualified Control.Arrow as Arrow import Control.Monad import Control.Monad.ST import Data.Bool import qualified Data.Char as Char import qualified GHC.Integer.GMP.Internals as GMP import qualified Data.ByteString.Char8 as BSC8 import qualified Data.Vector as V import qualified Data.Vector.Unboxed as VU import qualified Data.Vector.Unboxed.Mutable as VUM main :: IO () main = do n <- parse1 forM_ [1..n] $ \_ -> do (a, b, m) <- parse3 print $ tetration a b m tetration :: Int -> Int -> Int -> Int tetration a b m | m == 1 = 0 | a == 0 = bool 0 1 (even b) | b == 0 = 1 | b == 1 = a `mod` m | b == 2 = powModInt (a `mod` m) a m | otherwise = powModInt (a `mod` m) (prev + phi) m where !phi = eulerPhi m prev = tetration a (b - 1) phi powModInt :: Int -> Int -> Int -> Int powModInt a b c = fromInteger $ GMP.powModInteger (fromIntegral a) (fromIntegral b) (fromIntegral c) eulerPhi :: Int -> Int eulerPhi n = runST $ do xs <- VU.unsafeThaw $ VU.fromList [n, n, 2] ys <- loopFor xs p <- VUM.unsafeRead ys 0 q <- VUM.unsafeRead ys 1 if q > 1 then return (p - p `div` q) else return p where loopFor :: VUM.STVector s Int -> ST s (VUM.STVector s Int) loopFor xx = do idx <- VUM.unsafeRead xx 2 if idx * idx > n then return xx else do xret <- VUM.unsafeRead xx 0 xn <- VUM.unsafeRead xx 1 if xn `mod` idx /= 0 then do VUM.unsafeWrite xx 2 (idx + 1) loopFor xx else do VUM.unsafeWrite xx 0 (xret - xret `div` idx) whileXS <- loopWhile xx VUM.unsafeWrite whileXS 2 (idx + 1) loopFor whileXS where loopWhile :: VUM.STVector s Int -> ST s (VUM.STVector s Int) loopWhile ks = do whileN <- VUM.unsafeRead ks 1 whileI <- VUM.unsafeRead ks 2 if whileN `mod` whileI /= 0 then return ks else do VUM.unsafeWrite ks 1 (whileN `div` whileI) loopWhile ks 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 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 Char.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 Char.isSpace) <$> BSC8.getLine return $ VU.unzip3 vectup