CodeIQの「スクエア・カルテット」で正解した自分のコードをとりあえず公開します。
問題はこちら。
2つの自然数の組 (a, b) が与えられたとき、自然数 x, y に関する次の方程式を考えます。
x^2 + a^2 = y^2 + b^2 … (※)
例えば、(a, b) = (3, 10) のとき、方程式(※)の解は (x, y) = (10, 3), (46, 45) の 2 組です。自然数の組 (a, b) に対し、方程式(※)の全ての解の x + y の和を F(a, b) と定義します。
例えば F(3, 10) = 10 + 3 + 46 + 45 = 104 です。
同様に、F(10, 50) = 3500、F(20, 100) = 15022 となることが確かめられます。
標準入力から、半角空白区切りで 2 つの自然数 a, b(1 ≦ a < b ≦ 105)が与えられます。
標準出力に F(a, b) の値を出力するプログラムを書いてください。
解く方針は次の通りです(模範解答の1つ目の方針と同じ)。
方程式(※)を変形すると
となり、右辺の値は標準入力で与えられます。に注意すると、
の約数を求める問題に帰着します。約数はしらみつぶしで調べます。
提出したコードは次の通りです。言語はRubyです。
include Math a, b = gets.split.map(&:to_i) c = b*b - a*a sum = 0 1.upto(sqrt(c)) do |i| if c%i == 0 then p = i q = c/i if p != q && p%2 == q%2 then x = (q+p)/2 y = (q-p)/2 sum += x + y #puts "#{x}, #{y}" end end end puts sum