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

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 };
}