[BOJ] 2737 - 연속 합

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

 

BOJ - 연속 합

문제 유형: 수학, 정수론

문제 난이도: Gold III

시간 제한: 1초

메모리 제한: 128MB

 

문제

대부분의 양의 정수는 적어도 2개 이상의 연속된 자연수의 합으로 나타낼 수 있다.

예를 들면 다음과 같다.

6 = 1 + 2 + 3

9 = 5 + 4 = 4 + 3 + 2

하지만, 8은 연속된 자연수 합으로 나타낼 수가 없다.

자연수 N이 주어졌을 때, 이 수를 적어도 2개 이상의 연속된 자연수의 합으로 나타낼 수 있는 경우의 수를 출력하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 N이며, 231보다 작다.

 

출력

각 테스트 케이스에 대해서 N을 적어도 2개 이상의 연속된 자연수의 합으로 나타내는 경우의 수를 출력한다.

 

풀이

정수 n을 k개로 배분하려 할때,

m, m+1, ... m + k-1의 꼴이다.

즉, m * k + (k-1)k/2 = n을 만족하는 k의 개수가 정답이다.

 

코드

C++

#include <bits/stdc++.h>
#define ll long long
using namespace std;

void solve() {
    int n;
    cin >> n;

    int ans = 0;
    for (ll k = 2; (k - 1) * k / 2 < n; k++) {
        int rest = n - (k - 1) * k / 2;
        if (rest % k == 0) ans++;
    }
    cout << ans << "\n";
}

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}