BOJ 12858 Range GCD
https://www.acmicpc.net/problem/12858 12858번: Range GCD 첫째 줄에 수열의 원소의 개수를 나타내는 하나의 자연수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에 수열의 각 원소를 나타내는 N개의 자연수가 주어진다. i번째로 등장한 자연수는 수열의 i번째 www.acmicpc.net gcd(a, b, c, d, e) = gcd(a, |b - a|, |c - b|, |d- c|, |e - d|) 임을 이용해야 한다. (이 부분이 핵심이다) 어떤 구간에 속한 모든 원소에 x를 더한 더하는 경우, 그 구간 내에서 이웃한 원소들 사이의 차이는 변화가 없다. 그 구간의 경계에 인접한 원소와의 차이에만 변화가 발생한다. GCD를 계산하기 위한 세그먼트 트리에는 인..
더보기