[编程题]求序列和

题目来源：牛客网

[编程题]序列和

给出一个正整数N和长度L，找出一段长度大于等于L的连续非负整数，他们的和恰好为N。答案可能有多个，我我们需要找出长度最小的那个。 例如 N = 18 L = 2： 5 + 6 + 7 = 18 3 + 4 + 5 + 6 = 18 都是满足要求的，但是我们输出更短的 5 6 7

输入描述: 输入数据包括一行： 两个正整数N(1 ≤ N ≤ 1000000000), L(2 ≤ L ≤ 100)

输出描述 : 从小到大输出这段连续非负整数，以空格分隔，行末无空格。如果没有这样的序列或者找出的序列长度大于100，则输出No

输入例子: 18 2

输出例子 : 5 6 7

#include <iostream> #include <math.h> using namespace std; typedef unsigned long long LL; int main() { LL result = 0; int number = 0; cin >> result >> number; int startNum = 0; int minNum = 101; if (result >= 1 && result <= 10e9 && number >= 2 && number <= 100 && result >= number) { for (int i = number - 1; i < 100; i++) { LL q1 = 2 * result - i*i - i; LL q2 = 2 * (i + 1); if (q1%q2 == 0) { startNum = q1 / q2; minNum = i; while (minNum--) { cout << startNum << " "; startNum++; } cout << startNum << endl; return 0; } } } cout << "No" << endl; return 0; }

设满足条件的子序列起点数为a，最大增量为x，依据求和公式得： (a+a+x)(x+1)/2=N –>a=N/(x+1)-x/2

如果直接使用上式，判断N%(x+1)==0, x%2==0，这样做是错误的，最终在测试4950 100时会失败。

正确做法是继续合成单个分式：

a=(2N-x^2-x)/2(x+1)

即可成功通过测试