백준 2737번, 연속 합 풀이

문제

백준 2737번

풀이

$n$을 $a$부터 $b$까지의 합으로 나타내면 아래와 같습니다.

 

$$ n = a + a + 1 +\ \cdot\cdot\cdot \ + b - 1 + b $$

 

$a$부터 $b$까지 $k$개를 뽑는다고 하면 첫째항이 $a$이고 끝항이 $a + k - 1$가 되며, 등차가 1입니다.

등차수열의 합 공식에 의해서

 

$$ n = \frac{k(2a + k - 1)}{2} $$

 

로 나타낼 수 있습니다. 식을 정리하면

 

$$ k^2 + k(2a - 1) - 2n = 0 $$

 

으로 나타낼 수 있고, 근의 공식에 의해서

 

$$ k = \frac{1 - 2a \pm \sqrt{4a^2 - 4a + 1 + 8n}}{2} $$

 

이 됩니다. 뽑는 수 $k$를 최대로 하려면, 첫째항 $a$를 $ 1$로 두면 됩니다.

따라서, $k$의 범위는

 

$$ 2 \leq k \leq \frac{-1 + \sqrt{8n + 1}}{2} $$

 

 

$k$가 정해지면, $a$의 값 역시 구할 수 있습니다. 위 2차 방정식을 $a$에 대해 정리하면,

 

$$ a = \frac{n}{k} - \frac{k}{2} + \frac{1}{2} $$

 

위와 같습니다.

 

문제에서 $n$의 범위가 $2^{31}$보다 작다고 하였기 때문에 $k$의 최댓값은 $O(\sqrt{n})$ 이므로 시간 내에 통과할 수 있습니다.

소스코드

#include <bits/stdc++.h>

#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef unordered_map<int, int> mpii;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int T = 1;
	cin >> T;
	while (T--) {
		ld n;
		cin >> n;
		ld lim = (-1 + sqrt(8 * n + 1)) / 2; //k의 최댓값
		int ans = 0;
		for (ld k = 2; k <= lim; k++) {
			ld a = -(k / 2) + 0.5 + (n / k);
			if (a == (ll)a) ans++;
		}
		cout << ans << "\n";
	}
}