結果
問題 | No.1232 2^x = x |
ユーザー | かりあげクン |
提出日時 | 2020-09-21 13:56:32 |
言語 | Haskell (9.8.2) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,717 bytes |
コンパイル時間 | 7,893 ms |
コンパイル使用メモリ | 212,408 KB |
実行使用メモリ | 13,816 KB |
最終ジャッジ日時 | 2023-09-06 17:07:40 |
合計ジャッジ時間 | 11,830 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
7,272 KB |
testcase_01 | AC | 172 ms
11,452 KB |
testcase_02 | TLE | - |
testcase_03 | -- | - |
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.6.1/environments/default [1 of 2] Compiling Main ( Main.hs, Main.o ) Main.hs:36:37: warning: [GHC-68441] [-Wdeprecations] In the use of ‘powModInteger’ (imported from GHC.Integer.GMP.Internals): Deprecated: "Use integerPowMod# instead" | 36 | powModInt a b c = fromInteger $ GMP.powModInteger (fromIntegral a) (fromIntegral b) (fromIntegral c) | ^^^^^^^^^^^^^^^^^ [2 of 2] Linking a.out
ソースコード
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 xs <- parseN n VU.mapM_ (print . solve) xs solve :: Int -> Int solve i | i == 2 = 2 | otherwise = tetration 2 30 (i * (i - 1)) 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) {-# INLINE powModInt #-} 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