「ステップ・アップ・サム」問題 解説
CodeIQでの14問目の出題、「ステップ・アップ・サム」問題の解説です。
問題文はこちら。
自然数 n を連続する自然数の和で表す問題です。
先頭の自然数を a、自然数の個数を m とおきます。すると、自然数の和は次のようになります。
これが n に等しくなる a と m の組を全て求めればよいわけです。
この式をじっと見てみると、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