829. 连续整数求和
题目描述
输入正整数 n。
把 n 写成一段连续正整数的和，例如 9 = 2 + 3 + 4。只含 n 自身一个数也算一种写法。
返回这样的写法共有多少种。
输入：n = 5 输出：2
解释：5 和 2+3 两种。
输入：n = 9 输出：3
解释：9、4+5、2+3+4 三种。
输入：n = 15 输出：4
解释：15、7+8、4+5+6、1+2+3+4+5 四种。
数据范围
1 <= n <= 10^9
解题思路：枚举项数 k
设用 k 个连续正整数，首项为 x ≥ 1，则 n = kx + k(k-1)/2，即 x = (n - k(k-1)/2) / k。只要它是正整数就是一种方案。x ≥ 1 等价于 k(k+1)/2 ≤ n，所以只需枚举 k 到约 √(2n)，判断 n - k(k-1)/2 能否被 k 整除。
为什么正确
每个合法的 k 恰好对应一种方案（首项由 k 唯一确定），因此方案数 = 满足整除条件的 k 的个数。
复杂度分析
时间 O(√n)，k 最多约 √(2n)；空间 O(1)。
易错点
直接枚举首项和长度是 O(n) 甚至 O(n²)，n 达 10^9 会超时；另外 k(k+1)/2 在 C++/Java 里可能溢出 int，k 要用 long。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def consecutiveNumbersSum(self, n: int) -> int:
ans = 0
k = 1
while k * (k + 1) // 2 <= n:
if (n - k * (k - 1) // 2) % k == 0:
ans += 1
k += 1
return ansclass Solution {
public int consecutiveNumbersSum(int n) {
int ans = 0;
long k = 1;
while (k * (k + 1) / 2 <= n) {
if ((n - k * (k - 1) / 2) % k == 0) {
ans++;
}
k++;
}
return ans;
}
}class Solution {
public:
int consecutiveNumbersSum(int n) {
int ans = 0;
long long k = 1;
while (k * (k + 1) / 2 <= n) {
if ((n - k * (k - 1) / 2) % k == 0) {
ans++;
}
k++;
}
return ans;
}
};func consecutiveNumbersSum(n int) int {
ans := 0
k := 1
for k*(k+1)/2 <= n {
if (n-k*(k-1)/2)%k == 0 {
ans++
}
k++
}
return ans
}var consecutiveNumbersSum = function(n) {
let ans = 0;
let k = 1;
while (k * (k + 1) / 2 <= n) {
if ((n - k * (k - 1) / 2) % k === 0) {
ans++;
}
k++;
}
return ans;
};function consecutiveNumbersSum(n: number): number {
let ans = 0;
let k = 1;
while (k * (k + 1) / 2 <= n) {
if ((n - k * (k - 1) / 2) % k === 0) {
ans++;
}
k++;
}
return ans;
}其他解法
枚举 k 直接从等差数列公式出发，容易想到；奇因子计数把问题转化为经典的因子个数问题，数学性更强。
解法 2：统计奇因子个数 时间 O(√n)，空间 O(1)
由 n = k·x + k(k - 1)/2 得 2n = k·(2x + k - 1)，两个因子 k 与 2x + k - 1 奇偶性相反、且大的那个大于小的那个。可以证明每个合法表示一一对应 n 的一个奇因子，所以答案就是 n 的奇因子个数。先去掉 n 中所有的因子 2，再对剩下的奇数质因数分解，答案是各质因数指数加 1 后的乘积。
最坏情况同为 O(√n)，但 n 含小质因数时会很快缩小，实际更快。结论优美，但需要一段数论推导才能看出来，不如枚举 k 直观。
class Solution:
def consecutiveNumbersSum(self, n: int) -> int:
while n % 2 == 0:
n //= 2
ans = 1
p = 3
while p * p <= n:
e = 0
while n % p == 0:
n //= p
e += 1
ans *= e + 1
p += 2
if n > 1:
ans *= 2
return ansclass Solution {
public int consecutiveNumbersSum(int n) {
while (n % 2 == 0) n /= 2;
int ans = 1;
for (long p = 3; p * p <= n; p += 2) {
int e = 0;
while (n % p == 0) {
n /= p;
e++;
}
ans *= e + 1;
}
if (n > 1) ans *= 2;
return ans;
}
}class Solution {
public:
int consecutiveNumbersSum(int n) {
while (n % 2 == 0) n /= 2;
int ans = 1;
for (long long p = 3; p * p <= n; p += 2) {
int e = 0;
while (n % p == 0) {
n /= p;
e++;
}
ans *= e + 1;
}
if (n > 1) ans *= 2;
return ans;
}
};func consecutiveNumbersSum(n int) int {
for n%2 == 0 {
n /= 2
}
ans := 1
for p := 3; p*p <= n; p += 2 {
e := 0
for n%p == 0 {
n /= p
e++
}
ans *= e + 1
}
if n > 1 {
ans *= 2
}
return ans
}var consecutiveNumbersSum = function(n) {
while (n % 2 === 0) n /= 2;
let ans = 1;
for (let p = 3; p * p <= n; p += 2) {
let e = 0;
while (n % p === 0) {
n /= p;
e++;
}
ans *= e + 1;
}
if (n > 1) ans *= 2;
return ans;
};function consecutiveNumbersSum(n: number): number {
while (n % 2 === 0) n /= 2;
let ans = 1;
for (let p = 3; p * p <= n; p += 2) {
let e = 0;
while (n % p === 0) {
n /= p;
e++;
}
ans *= e + 1;
}
if (n > 1) ans *= 2;
return ans;
}