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 (+) 0.fromList.concatMap (goldenTriple k) $ [2,1,-1,-2]
         in numerator t + denominator t

main :: IO ()
main = print.p180 $ 35