题目描述

给定一个正整数N，将其写成多个连续正整数加和的形式。问一共有多少种这样的形式。

样例

输入: 5
输出: 2
解释: 5 = 5 = 2 + 3

输入: 9
输出: 3
解释: 9 = 9 = 4 + 5 = 2 + 3 + 4

输入: 15
输出: 4
解释: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

算法

(数学) $O(\sqrt {n})$

对于一个正整数$N$，如果能写成$K$个连续正整数相加的形式，则有，
$$ N = (x + 1) + (x + 2) + … + (x + K) $$
$$ N = K * x + \frac{(1 + K) * K}{2} $$
于是，N能够写成K个连续正整数相加的条件是，$(N - \frac{K * (K + 1)}{2})$能够被$K$整除。

时间复杂度分析：$K$个连续正整数相加，K的取值从$1$开始，且满足$(N - \frac{K * (K + 1)}{2})$大于等于0。$K$的可取值范围为$\sqrt {n}$量级。

C++ 代码

int consecutiveNumbersSum(int N) {
    int result = 0;
    for (int k = 1; k * (k + 1) <= 2 * N; k++) { 
        if ((N - k * (k + 1) / 2) % k == 0) result++;
    }
    return result;
}