本文由本人@takooctopus对LeetCode每日打卡签到，做点记录。
829. Consecutive Numbers Sum
题目描述
Given a positive integer N, how many ways can we write it as a sum of consecutive positive integers?
Example
| 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:
{{- code -}}
Solution
{{- code -}}
题设为
\begin{align}
N = n + n+1 + n+2 + … + n+d-1
\end{align}
我们合并同类项
\begin{align}
N = n * d + \frac{d * (d-1)}{2}
\end{align}
转化即
\begin{align}
n * d = N - \frac{d * (d-1)}{2}
\end{align}
只要 左边能被d整除，我们就能判定这个成立.