📝 문제 정보#
🧐 관찰 및 접근#
- $\text{gcd}(n, n+1)$은 몇일까?
- $G = gcd(n, n+1)$이 어떤 소수 $p$를 약수로 가진다고 하자.
- 이때 $p$는 간격 $p$마다 한개씩 존재한다.
- $p = 2$면 $p$를 약수로 가진 수는 $2$칸마다 존재한다.
- 따라서 연속된 두 수는 어떤 공약수인 소수 $p$를 가질 수 없다!
- 이때 $p$는 간격 $p$마다 한개씩 존재한다.
- 따라서 $\text{gcd}(n, n+1) = 1$임을 알 수 있다.
- $G = gcd(n, n+1)$이 어떤 소수 $p$를 약수로 가진다고 하자.
- 같은 방법으로, $\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';
}
}
}