题目描述

给定一个正整数 n，返回 连续正整数满足所有数字之和为 n 的组数。

样例

输入: n = 5
输出: 2
解释: 5 = 2 + 3，共有两组连续整数([5],[2,3])求和后为 5。

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

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

限制

• 1 <= n <= 10^9

算法

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

1. 假设首项为 $x$，项数为 $k$，根据数列求和公式 $sum = \frac{k(2x+k-1)}{2}$。
2. 令 $sum=n$，则可以枚举 $2n$ 的约数，将其分为两部分的乘积，较小的那一部分作为 $k$，较大的部分作为 $2x+k-1$，如果解得 $x$ 是正整数，则答案加 $1$。

时间复杂度

• 枚举约数的个数，故时间复杂度为 $O(\sqrt n)$。

C++ 代码

class Solution {
public:
    int consecutiveNumbersSum(int n) {
        int ans = 0;

        n += n;

        for (int i = 1; i * i <= n; i++) {
            if (n % i != 0)
                continue;

            int x = n / i + 1 - i;

            if (x % 2 == 0 && x > 0)
                ans++;
        }

        return ans;
    }
};