Problem 188

Problem 188 - Project Euler
これは前に解いた．

import Number (factors)
import Data.List (group)

phi :: Integer -> Integer
phi = product.map f.group.factors
    where f ps@(p:_) = let n = length ps
                       in p^(n-1)*(p-1)

towerMod :: Integral a => Integer -> a -> Integer -> Integer
towerMod a _ 0  = 1
towerMod a 1 n  = a `mod` n
towerMod a (k+1) n = powMod a (towerMod a k $phi n) n

powMod :: (Integral a, Integral b) => a -> b -> a -> a
powMod a n m | n < 3  = a^n `mod` m
             | n >=3  = let (q,r) = divMod n 2
                            aq = powMod a q m
                        in aq*aq*a^r `mod` m

main :: IO ()
main = print.towerMod 1777 1855 $ 10^8

たしか，オイラーの定理とか使ってたはず．