1 題目： 連續整數求和

官方標定難度：難

給定一個正整數 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

提示:

$1<=n<=10^9???????$

2 solution

由于 n 較大，直接枚舉會超時，所以需要分析一下分解的條件：

 n 若分成 k 個整整相加：1 若 k 是奇數  <=>    n 是 k 的倍數  and  n >= k(k+1)/22 若 k 是偶數   <=>   n = mk + k/2  and  n >= k(k+1)/2

代碼

class Solution {/** n 分解成連續整數的和：n <= 1e9* n 若分成 k 個整整相加* 1 若 k 是奇數 <=> n 是 k 的倍數  and  n >= k(k+1)/2* 2 若 k 是偶數 <=> n = mk + k/2  and  n >= k(k+1)/2*/
public:int consecutiveNumbersSum(int n) {int cnt = 0;for(int k = 1; k * (k + 1) <= 2 * n; k++){if(k % 2){cnt += n % k == 0;}else{cnt += (n - k / 2) % k == 0;}}return cnt;}
};

結果