如何用C实现一个将整数分解成连续自然数的函数

Question

如何用C实现一个将整数分解成连续自然数的函数

Answer 1

解题过程和证明如下：
问题：已知sum等于从k开始连续n个正整数之和，求k。
连续n个正整数之和显然是等差数列的问题，我们有公式：
S={a_1}n+\frac{n(n-1)d}{2}，对于我们的问题，有d=1。
所以对于从k开始的n个正整数，他们的和为：
S={a_1}n+\frac{n(n-1)}{2}=\frac{1}{2}n^2+\frac{2k-1}{2}n
\Rightarrow \frac{1}{2}n^2+\frac{2k-1}{2}n-S=0 （式1）
再来考虑n的范围，显然当从1开始加的时候，n应当最大；而n的最小情况则是当S为奇数时，S=\frac{S-1}{2}+\frac{S+1}{2}这种情形。
所以我们计算最大的可能的最大值n_max（程序中的max_n），令a1=1，公差d=1带入公式，
S=n_{max}+\frac{n_{max}(n_{max}-1)}{2}=\frac{1}{2}n_{max}^2+\frac{1}{2}n_{max}
\Rightarrow \frac{1}{2}n_{max}^2+\frac{1}{2}n_{max}-S=0
用二次方程的求根公式，我们可以得到nf_{max}=-\frac{1}{2}+\sqrt{\frac{1}{4}+2S}。
得到的这个nf不一定是一个整数，我们向下取整就得到n_{max} = floor(nf_{max})。
然后对于范围n\in [2, n_{max}]内的所有正整数n，我们带入式1验证
\Rightarrow \frac{2k-1}{2}n=S-\frac{1}{2}n^2
\Rightarrow k=\frac{S}{n}-\frac{n-1}{2}
如果k是整数，那么k就是我们要求的一个解。