Problem 180

http://projecteuler.net/index.php?section=problems&id=180

式変形する。はじめはnの範囲が有界でなくて、戸惑ったが、フェルマーの定理だった。

import Control.Monad (guard,liftM)
import Data.Ratio (denominator,numerator,(%))
import Data.Set (fromList,fold)
getZ :: Int -> Rational -> Rational -> Maybe Rational
getZ 2 x y = sqrt' $ x^2+y^2
getZ 1 x y = Just $ x+y
getZ (-1) x y = Just $ (x*y)/(x+y)
getZ (-2) x y = liftM (x*y/).sqrt' $ x^2+y^2
sqrt' :: Rational -> Maybe Rational
sqrt' x = let a = floor.sqrt.fromIntegral.numerator $ x
b = floor.sqrt.fromIntegral.denominator $ x
in if x==(a%b)*(a%b) then Just (a%b) else Nothing
goldenTriple :: Integer -> Int -> [Rational]
goldenTriple k n = do x <- [a%b | a <-[1..k-1], b<-[a+1..k]]
y <- [a%b | a <-[1..k-1], b<-[max (a+1).floor $ x*(a%1)..k]]
let z = getZ n x y
guard.maybe False (w -> w<1 && denominator w<=k) $ z
maybe [] (return.(x+y+)) $ z
p180 :: Integer -> Integer
p180 k = let t = fold (+) .fromList.concatMap (goldenTriple k) $ [2,1,-1,-2]
in numerator t + denominator t
main :: IO ()
main = print.p180 $ 35