ScalaでProject Euler(112)

Problem 75

a = 2lmn b = l(m2 - n2) c = l(m2 + n2)
(m, n) = 1 m + nは奇数

に従えば簡単に直角三角形が列挙できるので、それで長さについてカウントしていくだけですね。

def gcd(m :Int, n :Int) :Int = if(n == 0) m else gcd(n, m % n)

def right_triangles(Lmax :Int) :Iterator[(Int,Int,Int)] =
    for(l <- Iterator.range(1, Lmax / 12 + 1);
        m <- Iterator.from(2).takeWhile(m => 2 * l * m * (m + 1) <= Lmax);
        n <- Iterator.range(1, m).takeWhile(n => 2 * l * m * (m + n) <= Lmax)
                                        if (m + n) % 2 == 1 && gcd(m, n) == 1)
            yield (2 * l * m * n, l * (m * m - n * n), l * (m * m + n * n))

val N = 1500000
val count_length = new Array[Int](N + 1)
for((a, b, c) <- right_triangles(N))
    count_length(a + b + c) += 1
println (Iterator.range(2, N + 1, 2).count(n => count_length(n) == 1))