CodeIQ「ステップ・アップ・サム問題」に挑戦したようです

codeiq.jp

■問題

自然数 n を、2つ以上の連続する自然数の和で表すことを考えましょう。

 

例えば、18 は 5 + 6 + 7 や 3 + 4 + 5 + 6 と表すことができます。

同様に、15 は 7 + 8 や 4 + 5 + 6 や 1 + 2 + 3 + 4 + 5 と表すことができます。

いずれもこれら以外の表し方は存在しません。

 

この表し方における最も小さな数（上で太字で記した数のことです）を、全ての表し方について和をとったものを F(n) と定義します。

 

例えば F(18) = 5 + 3 = 8、F(15) = 7 + 4 + 1 = 12 です。

同様に、F(105) = 139、F(256) = 0、F(945) = 1698 であることが確かめられます。

 

標準入力から、自然数 n（1 ≦ n ≦ 1010）が与えられます。

標準出力に F(n) の値を出力するプログラムを書いてください。

■コード

いつも通りrubyで。

def f(x)
  i = 2
  res = 0
  while i*(i+1) <= 2*x
    if (i%2 == 0)
      res += x/i-i/2+1 if (x%i == i/2)
    else
      res += x/i-i/2 if (x%i == 0)
    end
    i+=1
  end
  res
end

while str = STDIN.gets
  puts f(str.to_i)
end

今回は前回と比べて難易度低めだった。

■方針

nをi個の連続する自然数の和で表す事を考える。

iが奇数の時

例えばi=3の時、n=3mと表せるとする。以下のように変形すると

n=m+m+m=(m+1)+m+(m-1)

となり、nが3の倍数の時は連続する3つの自然数の和で表すことができる。
n=5,7,9,11...の時も同様に、5,7,9,11...個の自然数の和で表せる。

また、最小値はm-(i/2(小数切り捨て))となる。

iが偶数の時

例えばi=4の時、n=4mと表せるとする。以下のように変形すると、

n=m+m+m+m=(m+3/2)+(m+1/2)+(m-1/2)-(m-3/2)

となり、nが4の倍数の時はm+3/2,m+1/2,m-1/2,m-3/2が自然数となるならば、連続する4つの自然数の和で表すことができる。
つまり、mが整数+1/2であればよく、nをiで割った時の余りがi/2であればこれを満たす。
n=2,6,8,10,12...の時も同様。

最小値はm(小数切り捨て)-i/2+1となる。

nをi個の連続する自然数の和で表すとき、iが最大になるのは1から足していく場合なので、公式より

i*(i+1) <= 2*n

をiが満たす間繰り返し、最小値の合計を求めると答えが得られる。