题目描述
给定一个正整数N,将其写成多个连续正整数加和的形式。问一共有多少种这样的形式。
样例
输入: 5
输出: 2
解释: 5 = 5 = 2 + 3
输入: 9
输出: 3
解释: 9 = 9 = 4 + 5 = 2 + 3 + 4
输入: 15
输出: 4
解释: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
算法
(数学) O(√n)
对于一个正整数N,如果能写成K个连续正整数相加的形式,则有,
N=(x+1)+(x+2)+…+(x+K)
N=K∗x+(1+K)∗K2
于是,N能够写成K个连续正整数相加的条件是,(N−K∗(K+1)2)能够被K整除。
时间复杂度分析:K个连续正整数相加,K的取值从1开始,且满足(N−K∗(K+1)2)大于等于0。K的可取值范围为√n量级。
C++ 代码
int consecutiveNumbersSum(int N) {
int result = 0;
for (int k = 1; k * (k + 1) <= 2 * N; k++) {
if ((N - k * (k + 1) / 2) % k == 0) result++;
}
return result;
}
写得很好,赞一个!