[leetcode] 829. Consecutive Numbers Sum

[leetcode] 829. Consecutive Numbers Sum

Description

Given a positive integer N, how many ways can we write it as a sum of consecutive positive integers?

Example 1:

Input: 5Output: 2Explanation: 5 = 5 = 2 + 3

Example 2:

Input: 9Output: 3Explanation: 9 = 9 = 4 + 5 = 2 + 3 + 4

Example 3:

Input: 15Output: 4Explanation: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

Note: 1 <= N <= 10 ^ 9.

分析

题目的意思是：给定一个数，分解成几个连续自然数的和，求分解方式的数目。

设 x + (x+1) + (x+2)+…+ k terms = N kx + k*(k-1)/2 = N kx = N - k*(k-1)/2 N - k*(k-1)/2 > 0 推出 k*(k-1) < 2N 这可以近似的用如下式子表示： k*k < 2N ==> k < sqrt(2N)

这道题的是leetcode上的hard题目，暴力破解会超时，关键在于数学推导，代码很简洁，我也做不出来，在这里学习一下。

代码

class Solution {public: int consecutiveNumbersSum(int N) { int count=1; for(int k=2;k

参考文献

​​[LeetCode] Complex Number Multiplication 复数相乘​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。