信息

• 题目: 829. 连续整数求和
• 标签: 数学

题解

根据等差数列的公式, 可以得到以下推导,
假定起始项为\(a\), 差\(d\)为1 项数\(k\), 和为\(n\), 则
$$
n = \frac{k \times (a+a+(k-1))}{2}
$$

等式变化可以得到

由于题目要求起始项 \(a\) 需要为正整数, 也就是\(2a + k - 1\)为正整数, 因此 2 * n % k == 0

同时有\(2a \ge 2\), 所以 \(2a + k - 1 \ge k + 1 \Rightarrow \frac{2n}{k} \ge k + 1\)

综上,
* \(k\)为\(2n\)的约数, 且是较小的那个.
* 因此在\([1, \sqrt{2n}]\)的范围内找\(k\)即可.
* \(a\) 为正整数, 因此 (2n/k -k + 1) % 2 == 0

pub fn consecutive_numbers_sum(n: i32) -> i32 {
    let mut ans = 0;
    let n = 2 * n;
    let mut k = 1;

    while k * k < n {
        if n % k != 0 {
            k += 1;
            continue;
        }
        if (n / k - (k - 1)) % 2 == 0 {
            ans += 1;
        }
        k += 1;
    }
    ans
}