« 2015年12月 | トップページ | 2016年2月 »

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の際はコード長短縮のために、必須ではないこの処理は省略しました。

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

| | コメント (0) | トラックバック (0)

« 2015年12月 | トップページ | 2016年2月 »