LC 829. 连续整数求和

传送门

题目

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

示例 1:

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

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

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

提示:

1 <= n <= 10^9

思路

简单的一个数学推导即可。因为这题的数据范围一看就知道不可能用dp来做，应该是有某个数学规律在的。

我们假设一段连续序列的首项是a，项数是k，那么我们根据等差数列求和公式可以得到
(a+a+k-1)*k/2 = n

(2a+k-1)*k = 2n

2a + k – 1 = 2n / k

2a = 2n/k – k + 1 >= 2

2n/k >= k+1
所以根据上面公式我们可以知道：由于a和k都是正整数，所以2a+k-1为正整数，所以2n/k要为正整数（k为2n的约数），并且由于2n/k >= k+1可知k还是较小的那个约数，此外由于2a一定为偶数，所以2n/k – k + 1一定为偶数，由上述即可条件我们即可通过枚举k的方式，来寻找答案，由于只用枚举到\sqrt(2n)，不会超时。

代码

class Solution {
public:
    int consecutiveNumbersSum(int n) {
        int ans = 0;
        n *= 2;
        for(int k = 1; k*k <= n; k++) {
            if(n % k) continue;
            if((n/k-k+1) % 2) continue;
            if(n/k-k+1>=2) ans++;
        }
        return ans;
    }
};