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

「ステップ・アップ・サム」問題 解説

 CodeIQでの14問目の出題、「ステップ・アップ・サム」問題の解説です。
 問題文はこちら

 自然数 n を連続する自然数の和で表す問題です。
 先頭の自然数a自然数の個数を m とおきます。すると、自然数の和は次のようになります。

 \begin{eqnarray} 
Sum &=& a+(a+1)+(a+2)+\cdots+(a+m-1) \\
&=& \sum_{i=1}^m (a+i-1) \\
&=& \frac{1}{2}m(2a+m-1)
\end{eqnarray}

 これが n に等しくなる am の組を全て求めればよいわけです。

 \begin{eqnarray} 
\frac{1}{2}m(2a+m-1) = n \\
m(2a+m-1) = 2n
\end{eqnarray}

 この式をじっと見てみると、2n が、m と 2a+m-1 の積であることが分かります。
 つまり、m は 2n の約数です。
 したがって、2n を割り切るような自然数を探せば、それが m の候補となります。

 そのような m を探すには、単純には、1 から 2n までの全ての自然数で 2n を割ってみればOKです。
 が、それでは長い計算時間を要してしまいます。
 そこで、「m が 2n の約数ならば 2n/m もまた 2n の約数である」という事実を利用します。
 したがって、1 から 2n まででなく、1 から √(2n) までの自然数で割り算を行えば十分です。

 m の候補が見つかれば、そのときの a の値も実際に求めてみて、題意を満たすかチェックしましょう。

 自分のコードはこちらです。

 挑戦者の方々のコードをまとめました。本問は、上記以外にもいろいろな解き方があると思います。
 ぜひ自分以外の人のコードを見て学んでみてください!
 togetter.com