(C++) - 백준(BOJ) 18005 : Even or Odd?

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

18005번: Even or Odd?

정수론 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

등차가 1인 연속 정수 구간의 길이 n을 선언 후 입력받습니다.

📔 풀이과정

2가지 경우가 있습니다. 

 

1. n이 홀수인 경우 : 연속 구간이 홀수라면 (짝수가 짝수개, 홀수가 홀수개), (짝수가 홀수개, 홀수가 짝수개) 두 경우이므로 누적합이 짝수 또는 홀수가 나오게 됩니다.

 

 2. 짝수인 경우 : 어떤 구간을 선택해도 짝수가 짝수개, 홀수가 짝수개의 형태로 나오게 됩니다. 따라서 그냥 1부터 n까지의 누적합 공식으로 짝수 홀수를 판별해줍니다. 공식은 다음과 같습니다.

 

$\displaystyle\sum\limits_{i=1}^{n} = \frac{n*(n+1)}{2} $ 

 

* n이 10억인 경우 시그마 공식을 적용하게 되면 (10억 * 10억1) / 2 이므로 int를 초과할 수 있으니 자료형을 적절히 선언해줘야 합니다.

📔 정답출력

 조건에 따라 출력해줍니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
ull n;
int main(){
    cin >> n;
    if(n % 2) cout << 0;
    else {
        if(n * (n+1) / 2 % 2) cout << 1;
        else cout << 2;
    }
}