문제 접근

이 문제는 구간 내에서의 최대公约수(GCD) 값을 구하는 문제이다. 핵심 아이디어는 차분(difference) 배열을 활용하는 것이다. 원래 배열에서 인접한 요소들의 차이를 구하면, 해당 구간의 GCD는 차분 배열의 특정 구간 GCD와 동일해진다.

따라서 우리는 구간 GCD를 효율적으로 구할 수 있는 자료구조를 사용하면 된다. 두 가지 대표적인 방법을 소개한다.

방법 1: 세그먼트 트리

세그먼트 트리를 사용하여 차분 배열의 구간 GCD를 유지한다. 각 노드에 해당 구간의 GCD 값을 저장하며, 점 업데이트와 구간 쿼리를 모두 O(log n) 시간에 처리할 수 있다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int MAXN = 200000 + 5;

ll arr[MAXN];

struct SegmentTree {
    int left, right;
    ll gcdValue;
} tree[MAXN * 4];

ll getGCD(ll a, ll b) {
    return std::gcd(a, b);
}

void applyNode(int idx) {
    tree[idx].gcdValue = getGCD(tree[idx * 2].gcdValue, tree[idx * 2 + 1].gcdValue);
}

void construct(int idx, int l, int r) {
    tree[idx].left = l;
    tree[idx].right = r;
    
    if (l == r) {
        tree[idx].gcdValue = 0;
    } else {
        int mid = (l + r) / 2;
        construct(idx * 2, l, mid);
        construct(idx * 2 + 1, mid + 1, r);
        applyNode(idx);
    }
}

void pointUpdate(int idx, int pos, ll value) {
    if (tree[idx].left == pos && tree[idx].right == pos) {
        tree[idx].gcdValue = value;
        return;
    }
    
    int mid = (tree[idx].left + tree[idx].right) / 2;
    if (pos <= mid) {
        pointUpdate(idx * 2, pos, value);
    } else {
        pointUpdate(idx * 2 + 1, pos, value);
    }
    applyNode(idx);
}

ll rangeQuery(int idx, int queryLeft, int queryRight) {
    if (tree[idx].left >= queryLeft && tree[idx].right <= queryRight) {
        return tree[idx].gcdValue;
    }
    
    ll result = 0;
    int mid = (tree[idx].left + tree[idx].right) / 2;
    
    if (queryLeft <= mid) {
        result = getGCD(result, rangeQuery(idx * 2, queryLeft, queryRight));
    }
    if (queryRight > mid) {
        result = getGCD(result, rangeQuery(idx * 2 + 1, queryLeft, queryRight));
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCases;
    cin >> testCases;
    
    while (testCases--) {
        int n, q;
        cin >> n >> q;
        
        for (int i = 1; i <= n; i++) {
            cin >> arr[i];
        }
        
        construct(1, 1, n);
        
        for (int i = 2; i <= n; i++) {
            ll diff = llabs(arr[i] - arr[i - 1]);
            pointUpdate(1, i, diff);
        }
        
        while (q--) {
            int l, r;
            cin >> l >> r;
            
            if (l == r) {
                cout << 0 << '\n';
            } else {
                cout << rangeQuery(1, l + 1, r) << '\n';
            }
        }
    }
    return 0;
}

방법 2: 희소 테이블 (Sparse Table)

희소 테이블은 정적 배열에서 구간 GCD를 O(1) 시간에 쿼리할 수 있는 자료구조이다. 전처리에 O(n log n)이 소요되지만, 각 쿼리는 상수 시간에 처리된다. 차분 배열을 미리 구축한 후 희소 테이블을 구성한다.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int MAXN = 200000 + 5;
const int LOG = 20;

ll inputArr[MAXN];
ll sparseTable[MAXN][LOG];
int log2Table[MAXN];
int numElements, numQueries;

int computeLog2(int x) {
    return 31 - __builtin_clz(x);
}

void preprocessLog2() {
    log2Table[0] = -1;
    for (int i = 1; i <= MAXN - 1; i++) {
        log2Table[i] = (i & (i - 1)) ? log2Table[i - 1] : log2Table[i - 1] + 1;
    }
}

void buildSparseTable() {
    for (int j = 1; j <= log2Table[numElements]; j++) {
        for (int i = 1; i <= numElements - (1 << j) + 1; i++) {
            sparseTable[i][j] = std::gcd(
                sparseTable[i][j - 1],
                sparseTable[i + (1 << (j - 1))][j - 1]
            );
        }
    }
}

ll queryGCD(int left, int right) {
    if (left > right) return 0;
    
    int length = log2Table[right - left + 1];
    return std::gcd(
        sparseTable[left][length],
        sparseTable[right - (1 << length) + 1][length]
    );
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    preprocessLog2();
    
    int testCases;
    cin >> testCases;
    
    while (testCases--) {
        cin >> numElements >> numQueries;
        
        for (int i = 1; i <= numElements; i++) {
            cin >> inputArr[i];
        }
        
        for (int i = 1; i <= numElements; i++) {
            sparseTable[i][0] = llabs(inputArr[i] - inputArr[i - 1]);
        }
        
        buildSparseTable();
        
        while (numQueries--) {
            int l, r;
            cin >> l >> r;
            cout << queryGCD(l + 1, r) << '\n';
        }
    }
    return 0;
}

핵심 정리

두 방법 모두 차분 배열을 구간 GCD 문제로 변환하는 아이디어를 활용한다. 세그먼트 트리는 동적 쿼리에 적합하고, 희소 테이블은 정적 데이터에서 다수의 쿼리가 있을 때 더 효율적이다. 문제의 요구사항에 맞게 적절한 방법을 선택하면 된다.