Problem 188

これは前に解いた．

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 _   = 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

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

コンテンツ