読者です 読者をやめる 読者になる 読者になる

プログラミングする数学信者

数学信者が数学とプログラミングの話題を中心にして何か書きます

CodeIQ「スクエア・カルテット」提出コード

Ruby プログラミング

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つ目の方針と同じ)。

方程式(※)を変形すると
(x+y)(x-y)=b^2-a^2
となり、右辺の値は標準入力で与えられます。x-y>0に注意すると、b^2-a^2の約数を求める問題に帰着します。約数はしらみつぶしで調べます。

提出したコードは次の通りです。言語は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