3つの辺の長さが全て整数の直角三角形で、3辺の長さの和（周長）が所定の値となる辺の組を考える。例えば周長が120となる直角三角形は(20,48,52), (24,45,51), (30,40,50) の3つである。周長1000以下の直角三角形で、最も多くの異なる辺の組を作れるのは周長がいくつのときか。
直角三角形を題材に三平方の定理を使う問題は以前も出た。
その時に使った知識がコチラ↓
a2 + b2 = c2 を満たす整数(a,b,c)は別の整数(u,v)を用いて
a = 2uv
b = u2 - v2
c = u2 + v2
と表すことができる。
今回もこれを使う。ただし1つ注意。上の(u,v)によって決まる(a,b,c)は、相似な直角三角形の中の1つを表すに過ぎず、今回のように周長が与えられている場合には、(u,v)の組に対して1つの三角形が定まるわけではない。例えば、(u,v) = (1,2)はお馴染みの(3,4,5)の直角三角形を表すが、周長が120だと実質(30,40,50)の組に対応する。問題は(u,v) = (2,4)はこれと相似な直角三角形(12,16,20)を表すが、これも周長が120に固定されているために、やはり(30,40,50)に対応するということだ。だから単純にa + b + c = 2u2 + 2uv = [周長]という条件を付しても上手く行かない。
これを回避するには、相似比rを導入して r*(a + b + c = 2u2 + 2uv) = [周長]という条件をリスト内包表記に加えることも可能だが、これだと結局3つの未知数を探索することになってしまい、辺の長さa,b,cを探索するのと計算量があまり変わらない。
以下では、(1,2)と(2,4)のように相似に該当するものを同一視する方法を取った。具体的には、(m,n)という組を見つけたら、mとnをそれらの最大公約数で割ることで、最も小さな直角三角形に対応する組として処理する。この辺の邪魔くささが、この問題の難所と言えば難所である。実際なかなか思うような結果が得られずに手こずった。
実はリスト内包表記の書き方で意外と苦戦した…★
