先日久しぶりに参加したCodeforces Round #368 (Div. 2) - Codeforcesの C. Pythagorean Triples が面白かったのでご紹介します。
問題
「正の整数aが与えられる。三平方の定理 a2 + b2 = c2 を満たす残りの 正の整数b, cの組を一組答えよ。そのようなb, cの組が存在しない場合は-1と出力せよ」
解答
少し考えてわからなかったのでググったところ、Pythagorean triple - Wikipedia, the free encyclopediaの"The Platonic sequence"に答がありました。これによると、
- aが奇数の場合：b = (a2 - 1)/2, c = (a2 + 1)/2
- aが偶数の場合：b = (a/2)2 - 1, c = (a/2)2 + 1
とすれば、三平方の定理を満たすピタゴラス数を生成できます。ただしaは3以上です。
導出
なぜこの方法でピタゴラス数を生成できるのかを考えてみます。まず、a2 + b2 = c2 を変形すると、a2 = (c - b) (c + b) となります。ここで、c - b, c + bは必ず偶奇が一致することに着目し、a2の偶奇に従って場合分けをします。
aが奇数の場合
c - b, c + bはともに奇数である必要があります。c - b = 1, c + b = a2 とするのが簡単で、連立方程式を解くと先に示した式になります。
aが偶数の場合
c - b, c + bはともに偶数である必要があります。c - b = 2, c + b = a2 / 2とするのが簡単で、連立方程式を解くと先に示した式になります。
注意
この方法ではすべてのピタゴラス数を列挙できるわけではないことに注意が必要です。例えば、(20, 21, 29)や(28, 45, 53)はこの方法では生成できません。
