Project Euler 091

http://projecteuler.net/problem=91
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2091

O(0,0), P(x1,y1), Q(x2,y2) 0<=x1,y1,x2,y2<=50
三角形OPQで異なる直角三角形は何個作れるか?

次のコードは自分で書いたもの。原点Oが直角になる場合とそうでない場合に分けて数え上げた。角Qが直角となるときの点Qの座標のリストで(0,0)を落としているのがあまりきれいじゃないと思う。

-- 点Qの座標のリスト
qs = drop 1 [(x,y)|x<- [0..50], y<- [0..50]]

-- 点Q(x,y) /= (0,0) とが直角となるような点Pで範囲内のもの
ps (x,y) = takeWhile p [(x-k*dx, y+k*dy)| k<- [1..]]
           ++ 
           takeWhile p [(x+k*dx, y-k*dy)| k<- [1..]]
    where dx = y `quot` (gcd x y)
          dy = x `quot` (gcd x y)

-- 点(a,b)が範囲内にあるか?
p (a,b) = 0 <= a && a <= 50 && 0 <= b && b <= 50

-- 原点Oが直角になる場合とそうでない場合に分けて和をとる
p091 =  (+) (50*50)  $ sum $ map (length.ps) qs 

main = print p091

次のコードはHaskellWikiのもの。直角となる点が軸上にある場合とそうでない場合に分けて数え上げている。数え上げればいい問題だからいちいち座標を計算する必要はないことがわかる。
http://www.haskell.org/haskellwiki/Euler_problems/91_to_100

reduce x y = (quot x d, quot y d)
  where d = gcd x y
 
problem_91 n = 
    3*n*n + 2* sum others
    where
    others =[min xc yc|
        x1 <- [1..n],
        y1 <- [1..n],
        let (yi,xi) = reduce x1 y1,
        let yc = quot (n-y1) yi,
        let xc = quot x1 xi
        ]