readme.md

カット・アンド・スクエア問題

CodeIQ の カット・アンド・スクエア問題 をやってみたので、自分なりの解き方を書いてみます。

問題の要約

ある数を上 n/2 桁と下 n/2 桁とに分け、それぞれを 2 乗して和をとると、元の数に戻ります。

例えば n = 4 の場合は、1233 と 8833 がこの条件を満たします。

12² + 33² = 1233

88² + 33² = 8833

設問

1. n = 6 の場合にこの条件を満たす数はただ一つ存在します。この数を求めてください。

2. 設問 n = 10 の場合にこの条件を満たす全ての数の総和を求めてください。

考え方

ある数の上 n/2 桁を x、下 n/2 桁を y とすると、それぞれを 2 乗して和をとると元の数に戻るためには、以下の等式が成り立つ必要があります。

x² + y² = x * 10^(n/2) + y

この式を変形すると次のようになります。

x * (10^(n/2) - x) = y * (y - 1)

右辺は y² に近いため、範囲内のすべての x に対して左辺の平方根を求め、それを整数化することで y を求め、それが上記の等式を満たすかを調べています。

コード

Ruby で書いたコードを添付します。ideone.com に 実際に動作するもの があります。

cut_and_square.rb

include Math

def main
  puts "6 digits"
  check_range((100..999), 1000)

  puts "10 digits"
  check_range((10000..99999), 100000)
end

def check_range(r, w)
  s = 0
  r.each do |x|
    org = get_org(x, w)
    if org != 0
      puts "matched: #{org}"
      s = s + org
    end
  end
  puts "sum: #{s}"
end

# check x^2+y^2==xxyy and returns original number or 0
def get_org(x, w)
  a = x * (w - x)
  y = sqrt(a).to_i + 1
  if a == y * (y - 1)
    return x * w + y
  else
    return 0
  end
end

main