Project Euler 解答

Project Euler Problem 097

Project Euler Problem 097

import Data.Char
n :: Integer
n = (28433*(2^(7830457))) + 1
ans1 :: Integer
ans1 = foldl ((+).(*10)) 0 $ map (fromIntegral . digitToInt) $ reverse $ take 10 $ reverse $ show n -- 8739992577 2sec

-- reverseとtakeを使うよりはdropのほうが短い
ans2 :: [Char]
ans2 = drop (length v - 10) v where v = show n

-- 単純なmodpow
modpow :: (Eq a1, Integral a, Num a1) => a -> a1 -> a -> a
modpow n k modulo = imp n k 1  where
  imp n 0 v = v
  imp n k v = imp n (k-1) ((v*n)`rem`modulo) 
-- 実際やってみると遅くなった。14.63sec  
ans3 :: Integer
ans3 = (28433*(modpow 2 7830457 (10^10))+1)`rem`(10^10)

-- successive squaringを実装したmodpow
modpow2 :: (Integral a1, Integral a) => a -> a1 -> a -> a
modpow2 n k modulo = imp n k 1 where
  imp n 0 v = v
  imp n k v | even k = imp (n*n) (k`quot`2) v
            | otherwise = imp n (k-1) ((v*n)`rem`modulo)
ans4 :: Integer
ans4 = (28433*(modpow2 2 7830457 (10^10))+1)`rem`(10^10)

-- 8739992577
main = print ans4

since 2013