취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 29279번 문제인 Поломка Бамблби이다.
문제는 아래 링크를 확인하자.

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

쿼리로 주어진 범위에 1이 아닌 수가 포함되어 있다면 그 수 하나만 포함된 구간의 mex값은 1이 되고, 따라서 gcd는 항상 1이 된다.

한편, 쿼리로 주어진 범위에 1만 포함되어 있다면 모든 구간의 mex값이 2가 되고, 따라서 gcd는 항상 2가 된다.

주어진 범위에 1이 아닌 수가 포함되어있는지 여부는 각 배열의 성분을 1인 경우와 아닌 경우 각각 0과 1을 부여한 배열의 누적 합을 계산해 두는 것으로 빠르게 판별할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, Q;
int A[100001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 1; i <= N; i++) {
        int x; cin >> x;
        if (x == 1) A[i] = A[i - 1];
        else A[i] = A[i - 1] + 1;
    }
    cin >> Q;
    while (Q--) {
        int L, R; cin >> L >> R;
        if (A[R] - A[L - 1]) cout << 1 << '\n';
        else cout << 2 << '\n';
    }
}