結果

問題 No.181 A↑↑N mod M
コンテスト
ユーザー こまる
提出日時 2020-10-24 05:19:09
言語 Haskell
(9.10.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,265 bytes
コンパイル時間 244 ms
コンパイル使用メモリ 148,992 KB
最終ジャッジ日時 2024-07-21 14:54:12
合計ジャッジ時間 569 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
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:5: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.
  |
5 | import qualified GHC.Integer.GMP.Internals         as GMP
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

ソースコード

diff # 

{-# LANGUAGE BangPatterns #-}

import           Data.Bool
import           Data.List
import qualified GHC.Integer.GMP.Internals         as GMP

main :: IO ()
main = do
  [a, b, n] <- map read . words <$> getLine
  print $ tetration a b n

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
  | a == 2 && b == 3 = 16 `mod` m
  | otherwise = powModInt (a `mod` m) (prev + phi) m
  where
    !phi = totient 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 #-}

totient :: Int -> Int
totient n = n `quot` product ps * (product $ map (subtract 1) ps)
  where ps = map head . group $ primeFactors n

smallPrimes :: [Int]
smallPrimes = 2 : [ n | n <- [3, 5 .. 46337], all ((0 <) . rem n) $ takeWhile (\x -> x * x <= n) smallPrimes]

primeFactors :: Int -> [Int]
primeFactors n | n < 2 = []
primeFactors n = go n smallPrimes
  where
    go !n pps@(p:ps)
      | n < p * p = [n]
      | r > 0     = go n ps
      | otherwise = p : go q pps
      where
        (q, r) = quotRem n p
    go n [] = [n]
0