C++で正整数Nを連続する正整数の和として表す方法の数を求める

正整数 N が与えられたとき、N を「1 つ以上の連続する正整数の和」として表現できるパターンが何通りあるかを求める問題を考えます。

例として、入力が 10 の場合を考えてみましょう。10 は次の 2 通りで表現できます。

• 10 = 1 + 2 + 3 + 4(4 つの連続する整数の和)
• 10 = 10(数そのもの 1 つ)

したがって、この場合の出力は 2 となります。

解法の考え方

N を「a から始まる i 個の連続する正整数の和」として表すことを、数学的に整理してみます。

a + (a + 1) + ... + (a + i − 1) = i × a + i × (i − 1) / 2 = N

この式から、a が正の整数になるためには、次の 2 つの条件を満たす必要があります。

• N − i × (i − 1) / 2 が i で割り切れること(a が整数になるため)
• i × (i + 1) / 2 ≤ N であること(a ≥ 1 を保証するため)

なお、i × (i + 1) / 2 と i × (i − 1) / 2 の差は i に等しいため、i を法とした剰余の判定ではどちらの式を使っても結果は同じになります。これが、コード内で sum = i × (i + 1) / 2 を用いても正しく動作する理由です。

アルゴリズムの手順

• ret := 1 で初期化します(N そのもの 1 つで表すケースを最初にカウント)
• i = 2 から順に、以下の処理を繰り返します
• sum := i × (i + 1) / 2(1 から i までの総和)を計算します
• sum > N になった時点でループを終了します
• rem := N − sum を計算します
• rem が i で割り切れる場合は、ret を 1 増やします
• 最後に ret を返します

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int consecutiveNumbersSum(int N) {
        int ret = 1;
        for(int i = 2; ; i++){
            int sum = (i * (i + 1)) / 2;
            if(sum > N) break;
            int rem = N - sum; ret += (rem % i == 0);
        }
        return ret;
    }
}; main(){
    Solution ob;cout << (ob.consecutiveNumbersSum(10));
}

入力

10

出力

2

計算量

ループは i × (i + 1) / 2 ≤ N が成り立つ間だけ実行されるため、反復回数は約 √(2N) 回です。したがって、時間計算量は O(√N)、空間計算量は O(1) となり、非常に効率的な解法といえます。