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
```
• はじめに
• プロジェクトオイラー問題
• リンク等