Project Euler 解答

Project Euler Problem 080

Project Euler Problem 080

import Data.List
import Data.Char

squares :: [Integer]
squares = [x^(2::Integer) | x<-[1..]]
dst :: [Integer]
dst = [1..100] \\ (takeWhile (<=100) squares) --テスト対象


-- 開平法。2桁専用
kaihei :: Integer -> [Integer]
kaihei d = imp 0 d where --dが3桁以上だと動かないので注意する
  imp v r = 
    let f x = x*(10*v+ x) in --左側に立てる式の計算
    let nextdigit = last $ takeWhile ((<=r).f) [0..9] in --右上に新たに解に加える値の計算
    let rhs = 100*(r - (f nextdigit)) in --右下の、引き算
    nextdigit : imp ((v*10+nextdigit)+nextdigit) rhs --次のイテレーション
dsum :: Integer -> Integer
dsum n = sum $ take 100 $ kaihei n
ans1 :: Integer
ans1 = sum $ map dsum dst

-- 40886
main :: IO ()
main = print ans1

-- http://www.shef.ac.uk/~pm1afj/maths/jarvisspec02.pdf
-- pdfのアルゴリズム
dbs :: (Num b, Num a, Ord a, Show a) => Int -> a -> [b]
dbs n d = map (fromIntegral . digitToInt) $ take n $ show $ snd $ foldl' (\a _ -> imp a) (5*d,5) [1..(10*n)] where
  imp (a,b) | a>=b = (a-b,b+10)
  imp (a,b) = (100*a,10*b-45)
ans2 :: Integer
ans2 = sum $ map (sum . dbs 100) dst

since 2013