2022-09-09：给定一个正整数 n，返回 连续正整数满足所有数字之和为 n 的组数 。 示例 1: 输入: n = 5 输出: 2 解释: 5 = 2 + 3，共有两组连续整数 ([5],[2,

2022-09-09：给定一个正整数 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

答案 2022-09-09：

如果有，N = (x+1) + (x+2) + ... + (x+k)上式子可以化简为：N = kx + k(k+1)/2 左右两边同时乘以 2，可以得到：2N = 2kx + k^2 + k 进而得到：2N = k(2x + k + 1)2N 偶 k * (2x + k + 1)k 2x + k + 1 所以，对于 2N = k(2x + k + 1)，这个式子来说，只要给定不同的一组 x 和 k，就对应一种不同的方案进一步分析可以看出：如果 k 为偶数，那么 2x + k + 1 就是奇数如果 k 为奇数，那么 2x + k + 1 就是偶数 2N = 左 K 右 2x + k + 12N 奇数因子 K, 2x + k + 1 也就是说，对于每一种方案，k 和 2x + k + 1，一定是不同的，并且连奇偶性都相反所以 2N 里任何一个奇数因子，可能作为 k 这一项，也可能作为 2x+k+1 这一项，不管奇数因子作为哪一项，都可以推出另外一项的值，进而确定 k 和 x 具体是多少进而可以推出，2N 里有多少个奇数因子，就有多少种方案于是这个题就变成了求 N 里有多少奇数因子一般来说，求 N 里有多少奇数因子，用 O(根号 N)的方法肯定可以但其实可以更加的优化，如果 N = 3^a * 5^b * 7^c * 9^d ....那么 N 一共会出现多少奇数因子呢？N 的质数因子：可以选择 0 个 3..可以选择 1 个 3...可以选择 2 个 3...可以选择 a 个 3，所以有 a+1 种选择上面的选择，去乘以：可以选择 0 个 5..可以选择 1 个 5...可以选择 2 个 5...可以选择 b 个 5，所以有 b+1 种选择上面的选择，去乘以：可以选择 0 个 7..可以选择 1 个 7...可以选择 2 个 7...可以选择 c 个 7，所以有 c+1 种选择...所以，一共有(a + 1) * (b + 1) * (c + 1) * (d + 1) .....这么多个奇数因子。

代码用 rust 编写。代码如下：

fn main() {    let n = 3 * 5 * 7;    let ans = consecutive_numbers_sum1(n);    println!("ans = {}", ans);    let ans = consecutive_numbers_sum2(n);    println!("ans = {}", ans);}
fn consecutive_numbers_sum1(mut n: i32) -> i32 {    while (n & 1) == 0 {        n >>= 1;    }    let mut res = 1;    let mut i = 3;    while i <= n {        let mut count = 1;        while n % i == 0 {            n /= i;            count += 1;        }        res *= count;        i += 2    }    return res;}
// 进一步优化fn consecutive_numbers_sum2(mut n: i32) -> i32 {    while (n & 1) == 0 {        n >>= 1;    }    let mut res = 1;    // O(根号N)    let mut i = 3;    while i * i <= n {        let mut count = 1;        while n % i == 0 {            n /= i;            count += 1;        }        // rest *= （计数+1）        res *= count;        i += 2    }    // N == 1表示已经找到了所有奇数因子    // N != 1表示只残留着最后一个奇数因子了    // 简单证明：如果N最后残留着不只一个奇数因子，    // 比如x*y(不妨设x<y)，那么在for循环里，就依然会有i*i <= N    // 因为i=x时，x*x <= x*y,所以x在for循环里就能计算到    // 所以如果N != 1表示只残留着一个奇数因子    return if n == 1 { res } else { res << 1 };}

执行结果如下：

左神java代码