[LeetCode][C++] #829. Consecutive Numbers Sum

[Medium][Question]:

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

Example 1:

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

Example 2:

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

Example 3:

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

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

My Solution[C++]:

[題目講解] ：幾種連續數字總和為N。

[Ideas]:

法一：Math method

大部分網路上的解法都是這個，這裡簡單講一下。

x起頭的連續數字，共有K個

x, x+1, x+2, ..., x+k-1

總和為N，根據等差公式可列出以下等式：

kx + (k-1)k / 2 = N

變形後可得到：

kx = N - (k-1)k / 2

法二：奇數偶數整除法

可由K個連續數字相加為N，K主要分為奇數/偶數

奇數 ：N可被K整除即為一種，因為奇數會有中間數

例如x-1, x ,x+1，共3個，所以總和為3x。

偶數 ： N被K除的餘數，若為K/2，也為一種

例如x-1,x, x+1, x+2，可看成x-1與x+2可調配成x,x+1，也就是有兩組x,x+1，也就是說(N-2)可被K整除。