跳转至

829. 连续整数求和#

问题描述#

给定一个正整数 N，试求有多少组连续正整数满足所有数字之和为 N?

示例 1:


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

示例 2:


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

示例 3:


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

说明: 1 <= N <= 10 ^ 9

解题思路#

假设 \(i+\dots+j=N\)，则有：

\[ \frac{(i+j)\times(j-i+1)}{2}=N \]

若 \(i+j\) 为奇数，则 \(j-i+1\) 为偶数；若 \(i+j\) 为偶数，则 \(j-i+1\) 为奇数。

也就是说，任意 \(\text{odd} \times \text{even}=2N\) 都满足条件，只要找出 \(2N\) 中的所有奇数因子就行。

找 \(2N\) 的奇数因子与找 \(2N\) 的最大的奇数因子的奇数因子的结果是一样的，因为每次除以 2 并不会改变奇数因子。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def consecutiveNumbersSum(self, N: int) -> int:
        while N & 1 == 0:
            N >>= 1 # N 的最大奇数因子

        ans = 0
        n = 1
        while n * n <= N:
            if N % n == 0:
                ans += 1
                m = N // n
                if m & 1 and m != n:
                    ans += 1
            n += 2

        return ans
测试数据
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
solution = Solution()

N = 5
assert solution.consecutiveNumbersSum(N) == 2

N = 9
assert solution.consecutiveNumbersSum(N) == 3

N = 15
assert solution.consecutiveNumbersSum(N) == 4

print("PASS!")
返回顶部

在手机上阅读