[1024] 수열의 합

https://www.acmicpc.net/problem/1024

처음에 나누는 수 L을 짝수일 때, 홀수일 때로 나눠서 나온 수를 수열의 가운데 있는 숫자라고 정하고,

그 수 앞뒤로 연속되는 숫자를 출력하는 방식으로 했는데 94%에서 틀렸습니다가 나왔다. 반례는 찾지 못했다.

수학적 지식이 있으면 쉽게 풀 수 있는 문제였다.

우선 N 은 길이가 L인 연속된 수의 합이다. 여기서 수열의 처음 시작인 x와 L을 알면 수열 리스트를 알 수 있다.

x를 구하기 위해서 다음과 같은 식을 세울 수 있다.

여기서 t는 1부터 L-1 까지의 합 (L-1) * L / 2의 식을 사용하면 쉽게 구할 수 있다.

이때,

x는 0보다 커야 하고,

N-t는 L로 나눈 나머지가 0이어야한다(정수).

---

#include <cstdio>

using namespace std;

int seqSum(int n)

{ //1부터 n 까지의 합

return n * (n + 1) / 2;

}

void showSeq(int n, int l)

{

for (int i = n; i < l + n; i++)

{

printf("%d ", i);

}

printf("\n");

}

int main()

{

int N, L = 0, x = -1;

scanf("%d %d", &N, &L);

for (int i = L; i <= 100; i++)

{

if ((N - seqSum(L - 1)) / L >= 0 && (N - seqSum(L - 1)) % L == 0)

{

x = (N - seqSum(L - 1)) / L;

showSeq(x, L);

return 0;

}

L++;

}

printf("-1\n");

return 0;

}