[BOJ] 백준 1024번: 수열의 합

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

1024번: 수열의 합

L 이상 100이하 길이의 연속된 수로 구성된 수열의 합이 N을 구하는 문제입니다.

도저히 풀이가 떠오르지 않아 모든 L에 대하여 이분탐색으로 가능한 경우의 수를 탐색했습니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
ll n, l;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> l;
	for (ll i = l; i <= 100; i++) {
		ll s = 0, e = 1000000000;
		ll mid;
		ll start = -1;
		while (s <= e) {
			ll mid = (s + e) / 2;
			ll sum = mid * i + (i*i - i) / 2;
			if (sum == n) {
				start = mid;
				break;
			}
			if (sum > n) {
				e = mid - 1;
			}
			else {
				s = mid + 1;
			}
		}
		if (~start) {
			for (ll j = start; j < start + i; j++) {
				cout << j << " ";
			}
			return 0;
		}
	}
	cout << -1;
}