« 「ルート・パワー問題」の高度じゃないコード | トップページ | 「プラス・マイナス・ゼロ問題」の高度じゃないコード »

2016年1月19日 (火)

「スクエア・カルテット問題」の高度じゃないコード

それでは、「高度じゃないコード」シリーズその3です。今回のお題は「スクエア・カルテット問題」です。その内容は次のようなものです。

2つの正整数 (a, b)(ただし、1 ≦ a < b ≦ 105)が与えられたとき、
等式 x2 + a2 = y2 + b2 を満たす
正整数解 (x, y) 全てにおける (x + y) の総和 f(a, b) を求めよ。

数学の問題をプログラミングで解こう!「スクエア・カルテット」問題解説

今回の問題は、「マヨイドーロ問題」や「ルート・パワー問題」と比べると比較的容易じゃないでしょうか?まず、この式のままでは扱いづらいので、x と y、a と b が同じ側に来るように移項すると等式は x2 - y2 = b2 - a2 になります。ここで、左辺を「和と差の積は平方の差」を使って因数分解すると (x + y) * (x - y) となり、求めるべき (x + y) が現れます。つまり、b2 - a2、または左辺と同様に因数分解した (b + a) * (b - a) を計算し、その定数 n を2つの整数の積で表せる組み合わせを探せばいいということになります。

ただし、和 (x + y) と差 (x - y) の両方が整数だからといって、x, y の両方が整数とは限りません。両方に 0.5 がついている可能性があるからです。しかし、x, y のいずれかが整数であれば、もう片方も整数であることは確定するので、和 (x + y) と差 (x - y) の和である 2 * x が偶数かどうか調べればいいことになります。(和と差の差である 2 * y が偶数かどうか調べても同じ)

最終的に欲しい値は和 (x + y) の方ですが、こちらは候補の数が多くなるので、ループで回すのは候補数の少ない差 (x - y) の方にします。さて、問題の等式を定数 n を使って書き直すと、n + y2 = x2 となることから、これは3辺の長さが (√n, y, x) の直角三角形となります。x は斜辺の長さであり √n は定数です。1 ≦ y < x なので y = 1 の時に y は最小ですが y が1大きくなっても、x の増分jは1未満なので、 (x - y) も y = 1 の時に最大となります。ただし、(x - y) = √n にはなりません。3辺の長さが (x - 1, 1, x) の直角三角形を描こうとしても一直線になってしまって描けないからです。よって、(x - y) < √n という条件で調べることになります。(直角三角形として考えなくても、式から明らかですが・・・)

さて、ここで、x, y が共に奇数、または、共に偶数の時は、和 (x + y) も差 (x - y) もその積 (x + y) * (x - y) も偶数となります。また、x, y の片方が奇数、もう片方が偶数の時は、和 (x + y) も差 (x - y) もその積 (x + y) * (x - y) も奇数となります。そこで、n が偶数の時は偶数だけを調べ、奇数の時は奇数だけを調べればいいわけです。なお、コードgolfの際はコード長短縮のために、必須ではないこの処理は省略しました。

ということで、Cで書いて提出したコードが以下のものとなります。上で説明した n は num、√n は sqr、(a - b) は sb、(a + b) は ad、そして、f(a, b) の集計には sum という変数を使っています。

コードgolfの方は、既に他の方がもっと短いコードを発表されていますが、一応、私が提出したのはこれです。初期値に 2 を入れてますが、最後に ~1 つまり -2 を加えることで相殺しています。

a,b=gets.split;n=b.to_i**2-a.to_i**s=2;p~1.upto(n**0.5-1){|i|s+=n/i+i&1|n%i>0?0:n/i}+s

|

« 「ルート・パワー問題」の高度じゃないコード | トップページ | 「プラス・マイナス・ゼロ問題」の高度じゃないコード »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/99795/63087919

この記事へのトラックバック一覧です: 「スクエア・カルテット問題」の高度じゃないコード:

« 「ルート・パワー問題」の高度じゃないコード | トップページ | 「プラス・マイナス・ゼロ問題」の高度じゃないコード »