BOJ 12858 Range GCD

📝 문제 정보

링크: https://www.acmicpc.net/problem/12858

🧐 관찰 및 접근

$\text{gcd}(n, n+1)$은 몇일까?
- $G = gcd(n, n+1)$이 어떤 소수 $p$를 약수로 가진다고 하자.
  - 이때 $p$는 간격 $p$마다 한개씩 존재한다.
    - $p = 2$면 $p$를 약수로 가진 수는 $2$칸마다 존재한다.
  - 따라서 연속된 두 수는 어떤 공약수인 소수 $p$를 가질 수 없다!
- 따라서 $\text{gcd}(n, n+1) = 1$임을 알 수 있다.
같은 방법으로, $\text{gcd}(a, b) = \text{gcd}(a, b-a)$ 임도 알 수 있다.
- 유클리드 호제법에서도 알 수 있듯이!
구간 쿼리지만, Lazy하게 연산하기는 쉽지 않아보인다.
- 하지만 $\text{gcd}(x_a, x_{a+1}, x_{a+2}, \dots, x_b)$ 를
- $\text{gcd}(x_a, x_{a+2} - x_{a+1}, x_{a+3} - x_{a+2}, \dots, x_b - x_{b-1})$
- 이라고 생각하면, 바뀌는 수는 생각보다 많지 않다!
Lazy한 합 연산과 최대공약수에 대한 그냥 세그먼트 트리로 풀 수 있지 않을까?
- 사실 Lazy부분도 구간 덧셈, 점 쿼리이므로 그냥 세그로 바꿀 수 있지만, 귀찮으니까 ㅋㅋ

💻 풀이

코드 (C++):


void solve(){
    int N; cin >> N;
    LazySegmentTree LST(N);
    ST.init(N-1);

    vector<ll> A(N);
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) LST.set(i, A[i]);
    LST.build();
    rep(i, 0, N-1) ST.set(i, abs(A[i+1] - A[i]));
    ST.build();

    int Q; cin >> Q;
    while(Q--){
        ll op, a, b; cin >> op >> a >> b;
        a--; b--;
        if(op){
            LST.update(a, b, op);
            if(a-1 >= 0) ST.update(a-1, abs(LST.query(a-1, a-1) - LST.query(a, a)));
            if(a+1 < N) ST.update(a, abs(LST.query(a+1, a+1) - LST.query(a, a)));
        }else{
            cout << gcd(LST.query(a, a), ST.query(a, b-1)) << '\n';
        }
    }
}