学步园

为了找份暑期实习生的工作，今天去某公司面试。很喜欢这样的公司，首先不问出身、不问爱好，直接给你一台电脑，几道编程题目，让你写程序。

其中有道题目是将一个整数分解为连续正整数之和，如15可以分解为：

15 = 1 + 2 + 3 + 4 + 5

15 = 4 + 5 + 6

15 = 7 + 8

这道题，我用最死板的方法给编出来了。输入数n，设置起始位置i，再遍历连续正整数的长度k，由公式计算出 sum = i + (i+1) + ... + (i+k) = (k+1) * (2*i + k) / 2，判断与n的关系，若相等则打印出从i到i+k这（k+1）个数；若sum>n，则break；

伪码如下：

for  (i = 1; i <= n/2; i++)

	for  (k = 1;  ; k++)

		sum = (k+1) * (2*i + k) / 2;

			if (sum > n)

				break;

			if (sum == n)

				print (从i到i+k的值)


但这算法的复杂度高呀！达到O（n2）！肯定不是最好的方法，回来我在网上找了一下这个题目，发现有很多解法，说一个比较容易理解的吧。
我们计算从i开始连续k个数之和的计算公式如下：
sum = k * (2 * i + k - 1) / 2;
现在题目要求sum == n 的所有可能情况，上面的解法是从起始位置开始循环，又根据连续个数循环，两重循环，那么从上面的公式逆向想想，如果sum==n时，i与k直接满足什么关系呢？有 k * (2 * i + k - 1) = 2 * n。那么如果用k循环，计算出起始位置 i = ( 2*n / k - k + 1) / 2，岂不是时间复杂度降到线性的了。如下：
for (k = 1; k <= n/2; k++)

	if (2*n % k == 0)      //能被k整除

		temp = 2*n / k - k + 1;

		if (temp % 2 == 0)      //能被2整除

			i = temp / 2;

			print (从i到i+k-1的值)
ok!